Rounding off to nearest power of 2

Question

I want to write a function that returns the nearest upper power of 2 number. For example if my input is 789, the output should be 1024. Is there any way of achieving this without using any loops but just using some bitwise operators?

Answer 1

Check the Bit twidding hacks. You need to get the base 2 logarithm, then add 1 to that.

Answer 2

See here for possible solutions: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float

Answer 3

next=pow(2, ceil(log(x)/log(2));

This works by finding the number you'd have raise 2 by to get x (take the log of the number, and divide by the log of the desired base, see wikipedia for more). Then round that up with ceil to get the nearest whole number power.

This is a more general purpose (i.e. slower!) method than the bitwise methods linked elsewhere, but good to know the maths, eh?

Answer 4

unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
}

Answer 5

If you need it for OpenGL related stuff:

/* Compute the nearest power of 2 number that is 
 * less than or equal to the value passed in. 
 */
static GLuint 
nearestPower( GLuint value )
{
    int i = 1;

    if (value == 0) return -1;      /* Error! */
    for (;;) {
         if (value == 1) return i;
         else if (value == 3) return i*4;
         value >>= 1; i *= 2;
    }
}

Answer 6

By way of clarification, do you need the nearest power of 2 (ie. 65 would give you 64, but 100 would give you 128) or the nearest above (ie. 65 would give you 128, and so would 100)?

Answer 7

The ultimate answer can be found at http://www.gamedev.net/community/forums/topic.asp?topic_id=229831

There are a few different ideas how to archive the desired result. Using loops, as in some of the examples here, is not at all necessary.

Answer 8

For IEEE floats you'd be able to do something like this.

int next_power_of_two(float a_F){
 int f = *(int*)&a_F;
 int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

 f >>= 23; // remove factional part of floating point number
 f -= 127; // subtract 127 (the bias) from the exponent

 // adds one to the exponent if were not a power of two, 
 // then raises our new exponent to the power of two again.
 return (1 << (f + b)); 
}

If you need an integer solution and you're able to use inline assembly, BSR will give you the log2 of an integer on the x86. It counts how many right bits are set, which is exactly equal to the log2 of that number. Other processors have similar instructions (often), such as CLZ and depending on your compiler there might be an intrinsic available to do the work for you.