将无符号整数舍入为2的幂序列

Question

我分配了大缓冲区,然后拆分成多个大小的块.这些尺寸从32开始,然后在每次增加时乘以2.

struct Node
{
    Node*           Next;
    void*           Data;
    const unsigned  Size;
};

Node* m_Buffers[16];

这意味着缓冲区m_Buffers[0]的大小为32,缓冲区m_Buffers[1]的大小为64,依此类推.

并且一个函数接受一个数字并返回一个指定数字可以舍入到的大小的缓冲区.

void * GetBuffer(unsigned size)
{
    // ...
}

例如,如果我请求一个384的缓冲区,那么我需要能够在512处将其舍入并从中返回缓冲区m_Buffers[4].

到目前为止,我正在使用循环来舍入:

void * GetBuffer(unsigned size)
{
    unsigned buffer_size = 32;

    while (buffer_size < size)
    {
        buffer_size *= 2;
    }

    // ...
}

但我很好奇是否有一种更好的方法可以不涉及循环.如果有一种方法可以将舍入数字转换为数组中的索引而不使用switch语句.

说实话,我甚至不确定标题是否正确.所以我为此道歉.

Answer 1

unsigned int v;
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

这个想法是"粘贴" v-1低于MSB本身的所有位置的最高位(MSB),这产生了^2k -1 的形式.之后,数字递增以得到最终结果.