Rounding up to nearest power of 2

Rounding up to nearest power of 2

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 by florin for Rounding up to nearest power of 2

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

Answer by Paul Dixon for Rounding up to nearest power of 2

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 by Eclipse for Rounding up to nearest power of 2

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++;      return v;    }  

Answer by Paulo Lopes for Rounding up to nearest power of 2

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 by Jasper Bekkers for Rounding up to nearest power of 2

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.

Answer by ydroneaud for Rounding up to nearest power of 2

If you're using GCC, you might want to have a look at Optimizing the next_pow2() function by Lockless Inc.. This page describes a way to use built-in function builtin_clz() (count leading zero) and later use directly x86 (ia32) assembler instruction bsr (bit scan reverse), just like it's described in another answer's link to gamedev site. This code might be faster than those described in previous answer.

By the way, if you're not going to use assembler instruction and 64bit data type, you can use this

/**   * return the smallest power of two value   * greater than x   *   * Input range:  [2..2147483648]   * Output range: [2..2147483648]   *   */  __attribute__ ((const))  static inline uint32_t p2(uint32_t x)  {  #if 0      assert(x > 1);      assert(x <= ((UINT32_MAX/2) + 1));