Round unsigned integer to a sequence of powers of two

Question

I have large buffer allocated and then split into chunks of multiple sizes. Those sizes start with 32 and then multiplying that by 2 with each increase.

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

Node* m_Buffers[16];

Which means that the buffers at m_Buffers[0] will be of size 32 and the buffers at m_Buffers[1] will be of size 64 and so on.

And a function that takes a number and returns a buffer of the size that the specified number can round up to.

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

For example, if I request a a buffer of 384 then I need to be able to round that at 512 and return a buffer from m_Buffers[4].

So far I'm using a loop to round up:

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

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

    // ...
}

But I'm curious if there's a better way of rounding up that doesn't involve a loop. And also if there's a way to convert the rounded number to an index in the array without using a switch statement.

And to be honest, I'm not even sure the title is correct. So I apologize for that.

Answer 1

You can use this bit triddling hack for that:

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

The idea is to "paste" the most significant bit (MSB) of v-1 in all positions lower than the MSB itself, which produces a number of the form 2^k-1. After that the number is incremented to arrive at the final result.

Answer 2

You can use a function to determine the next power of 2 without looping. See this link:

Next Power of 2