将无符号整数舍入为 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，依此类推。

还有一个函数，它接受一个数字和 return 一个大小为指定数字可以四舍五入的缓冲区。

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

例如，如果我请求一个 384 的缓冲区，那么我需要能够将其舍入到 512 和 return 来自 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++;

想法是 "paste" v-1 的最高有效位 (MSB) 在所有低于 MSB 本身的位置，它产生一个 2^{k 形式的数字}-1。之后数字递增得到最终结果。

Answer 2

您可以使用一个函数来确定下一个 2 的幂而无需循环。看到这个 link:

Next Power of 2

Round unsigned integer to a sequence of powers of two