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

Question

If I have a integer number n, how can I find the next number k > n such that k = 2^i, with some i element of N by bitwise shifting or logic.

Example: If I have n = 123, how can I find k = 128, which is a power of two, and not 124 which is only divisible by two. This should be simple, but it eludes me.

Answer 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).