Given an integer, how do I find the next largest power of two using bit-twiddling?

Solution 1:

For 32-bit integers, this is a simple and straightforward route:

unsigned int n;

n--;
n |= n >> 1;   // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2;   // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;           // The result is a number of 1 bits equal to the number
               // of bits in the original number, plus 1. That's the
               // next highest power of 2.

Here's a more concrete example. Let's take the number 221, which is 11011101 in binary:

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2;   // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4;   // ...
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

There's one bit in the ninth position, which represents 2^8, or 256, which is indeed the next largest power of 2. Each of the shifts overlaps all of the existing 1 bits in the number with some of the previously untouched zeroes, eventually producing a number of 1 bits equal to the number of bits in the original number. Adding one to that value produces a new power of 2.

Another example; we'll use 131, which is 10000011 in binary:

n--;           // 1000 0011 --> 1000 0010
n |= n >> 1;   // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2;   // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4;   // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8;   // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16;  //      operations produce no effect.)
n++;           // 1111 1111 --> 1 0000 0000

And indeed, 256 is the next highest power of 2 from 131.

If the number of bits used to represent the integer is itself a power of 2, you can continue to extend this technique efficiently and indefinitely (for example, add a n >> 32 line for 64-bit integers).

Solution 2:

There is actually a assembly solution for this (since the 80386 instruction set).

You can use the BSR (Bit Scan Reverse) instruction to scan for the most significant bit in your integer.

bsr scans the bits, starting at the most significant bit, in the doubleword operand or the second word. If the bits are all zero, ZF is cleared. Otherwise, ZF is set and the bit index of the first set bit found, while scanning in the reverse direction, is loaded into the destination register

(Extracted from: http://dlc.sun.com/pdf/802-1948/802-1948.pdf)

And than inc the result with 1.

so:

bsr ecx, eax  //eax = number
jz  @zero
mov eax, 2    // result set the second bit (instead of a inc ecx)
shl eax, ecx  // and move it ecx times to the left
ret           // result is in eax

@zero:
xor eax, eax
ret

In newer CPU's you can use the much faster lzcnt instruction (aka rep bsr). lzcnt does its job in a single cycle.