Jump to content
  • Advertisement


This topic is now archived and is closed to further replies.


Power of two problem

This topic is 5742 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a number x, and I want to find the next power of two that is larger than x. I know, x is NOT a power of two. I know, I could do this with while, but I wanted to do it with bitwise operators, when it can be done with them. Thanks, PM

Share this post

Link to post
Share on other sites

The bitwise operations available in languages like C or C++ are not very good for finding the most significant bit, which is basically your problem. Modern processors usually provide an instruction for this, though.

I can think of a way of doing it using bitwise operations:

unsigned next_power_of_2(unsigned x){ // Assume 32 bit integers

int i=0;
return (1u<<(i+1));

[edited by - alvaro on October 1, 2002 9:48:03 AM]

Share this post

Link to post
Share on other sites
The BSR instruction (Bit Search Reverse) searches for the place of the most significant bit of an operand. So it effectively give you the log2 of any positive integer rounded down. Add 1 to this and you have the log2 of the next highest power of 2. Shift the number 1 by this log and you have the next power of 2 larger than x.

unsigned int NextPowerOf2(unsigned int x)
unsigned int result = 0;
_asm bsr ecx,x; // Find the base 2 logarithm

_asm inc ecx; // Increase it by 1

_asm mov eax,1;
_asm shl eax,cl; // Find the antilogarithm

_asm mov result,eax;
return result; // Return the result


This function is very small and fast. Here''s one example of a problem which is difficult to solve in C, but really simple in assembly.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!