Archived

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

PM

Power of two problem

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
2^(ceil(log2(x)))

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;
if(x&0xffff0000){
x&=0xffff0000;
i+=16;
}
if(x&0xff00ff00){
x&=0xff00ff00;
i+=8;
}
if(x&0xf0f0f0f0){
x&=0xf0f0f0f0;
i+=4;
}
if(x&0xcccccccc){
x&=0xcccccccc;
i+=2;
}
if(x&0xaaaaaaaa){
x&=0xaaaaaaaa;
i+=1;
}
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