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

The key part here is that all powers of 2 in binary are 1 followed by zeroes.

10 = 2

100 = 4

1000 = 8

10000 = 16

So, functionally, what you want to do is add a 1 in the next greatest column of the binary number and set all the rest to 0.

Here's how I'd do it:

You need to shift to the right until you only have a 1 in the 2^0 column, then shift left the same number of times you originally shifted right, plus one.

1101 = 13

Use a recursive function, shift right, repeat until value is 1, keeping count of the shifts (3 in this case)

0001 (note that this does discard the less significant bits)

shift left four times

10000 = 16

One cautionary note, make sure you check to see if your input number is greater than zero; the recursive part will loop eternally if you give it a zero.

Answer 2

X=1

while (X<N)

{

shift the bits one place so that the number doubles

}

ex. N=123

X=1,2,4,8,16,32,64,129