There are many occasions when a programmer would want to calculate the next power of two for a given number. For me it was a bitonic sorting algorithm operating in a compute shader and I had this piece of code be responsible for calculating the next power of two of a number:

*uint myNumberPowerOfTwo = 1;*

*while( myNumberPowerOfTwo < myNumber)*

*{*

* myNumberPowerOfTwo <<= 1;*

*}*

It gets the job done, but doesn’t look so nice. For not unusual cases when *myNumber* is more than 1000 it can already take ten cycles to loop. I recently learned that HLSL has a built in function called firstbithigh. It returns the position of the first non zero bit in a 32-bit number starting from the left to the right (from high order to low). With its help, we can rewrite the algorithm as follows:

*uint myNumberPowerOfTwo = 2 << firstbithigh(myNumber);*

It does the same thing, so how does it work? Take a random number and write it in binary:

00000001011010011011011111000100

For that number, *firstbithigh* returns the number of the location of the first non zero bit (from the left), which is 24. The next power of two to that number would be:

00000010000000000000000000000000

That number has seven leading zeroes. All we have to do is zero the whole number but set a single bit to non-zero. To do it, first set up 2 in binary:

00000000000000000000000000000010

Then shift the whole thing left by the position of the first bit in *myNumber* to get what we are looking for:

00000010000000000000000000000000

Nice one, but we have a few corner cases we need to eliminate. If *myNumber* is already a power of two, we will get a greater power of two which might not be what we are looking for. In that case we should return *myNumber* itself. If you subtract one from *myNumber* before calling *firstbithigh* on it, it will ensure that power of two numbers will return themselves:

*uint myNumberPowerOfTwo = 2 << firstbithigh(myNumber – 1);*

Take 1024 for example, it will get the next power of two for 1023 which is 1024. Or take 129 for example, it will get the next power of two for 128 which is 256, so works out quite well. If you try to calculate it for 0 however, there is a potential bug if *myNumber* is unsigned, as -1 in unsigned would wrap around to *0xFFFFFFFF*. If you can potentially call it for zeroes and operate on unsigned, I would suggest doing it like this:

*uint myNumberPowerOfTwo = 2 << firstbithigh(max(1, myNumber) – 1);*

If it is signed int, then you don’t have to worry about it, as the *firstbithigh* function will return zero for negative numbers.

Have any question, noticed a mistake? Please post in the comments below!

Thank you for reading!

If you don’t have access to the firstbithigh intrinsic, it can also be done like this:

uint GetNextPower( float i_n )

{

return ((uint)ceil( sqrt( i_n ) ))

LikeLike

Oops forgot to quote code:

LikeLike

Hm, that doesn’t seem right, try that with a few numbers. I think you might have meant using log2 like this, which gives the correct result:

The difference is that log2 is a

~~half~~quarter-rate instruction as I know, while firstbithigh is full-rate. Although firstbithigh doesn’t work for floats like this.LikeLike

Great article. I’m looking at using this myself and noticed that an input value of 1 seems to results in a nextpoweroftwo of 0 on both my AMD machine and in C++. It seems like left shifting by a negative amount is undefined in C++. Does that seem right to you?

LikeLike