2

I came across a piece of code for finding the smallest power of 2 greater than a 32-bit integer n...

n+=(n==0);
n--;
n|=n>>1;
n|=n>>2;
n|=n>>4;
n|=n>>8;
n|=n>>16;
n++;

Now how does it work? I tried printing the number in base-2 after every step for n=100, but it didn't make much sense. What's the logic behind it?

sudeepdino008
  • 3,194
  • 5
  • 39
  • 73
  • 1
    I thought this was for a 32bit integer? – WhozCraig Jan 12 '13 at 07:30
  • It works only with 32-bit uint. BTW there was [same question](http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i): nextpow2 is same number if it is a power of two (`x & ( x – 1) == 0`) and its `msb << 1` otherwise. – Eddy_Em Jan 12 '13 at 07:41
  • @WhozCraig Yes. Sorry, i edit the question. – sudeepdino008 Jan 12 '13 at 08:02

3 Answers3

3

This piece of code fills all the least significant bits of the given number n with binary 1s and after that increases the result by 1, achieving the requested outcome. E.g., for input 101 the bit manipulations will yield 111 and after the increase by 1 it will become 1000(8), which is indeed the least power of 2 greater then 101(5).

Update: Actually, this is an optimization to the trivial method of just setting each lsb bit manually. Why this optimization achieves the same result is a different question in a broader scope which is beyond this question.

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
3

Actually it finds the smallest power of 2 greater or equal than n and it works for 32 bit unsigned numbers.

  • The first line just treats 0 the same way as 1 (written in a somewhat confusing way)
  • The second line accounts for the "or equal", if a number is exactly a power of two we make it one bit shorter.
  • the next few lines make sure, that all lower bits are set to 1. First we shift right by 1 and do a logical or. The effect is that now the highest bit and the bit immediately below are set to 1. Doing the same now with a shift of 2 makes the top 4 bits one, and so on.
  • finally we have a number that is one less than a power of two and we just add 1.
Henry
  • 42,982
  • 7
  • 68
  • 84
0

Additional to icepack's answer: As explained here, the algorithm calculates 1 << (floor(log_2(n - 1)) + 1).

filmor
  • 30,840
  • 6
  • 50
  • 48