#### Archived

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

# Power of two problem

## Recommended Posts

PM    122
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 on other sites
alvaro    21263
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 on other sites
Jaywalk    250
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.