Round up to the next highest power of 2

Given a number n, find next highest power of 2. If n itself is a power of 2, return n.

 

For example,

Input: n = 20
Output: 32
 

Input: n = 16
Output: 16
 


Approach 1:

The idea is to unset rightmost bit of n till only one bit is left which will be the last set bit of the given number. To handle the case when n itself is power of 2, we decrement n by 1 in the beginning. Note that this operation will not have any impact on output as we’re only concerned about last set bit of n.

 
C++ implementation –
 

Download   Run Code

Output:

Next power of 2 is 128

 

Approach 2:

The idea is to decrement n by 1 (to handle the case when n itself is power of 2) and run a loop by initializing the result by 2. At each iteration of loop, we double result value and divide n in half and continue the loop till n becomes 0.

 
C++ implementation –
 

Download   Run Code

Output:

Next power of 2 is 128

 

Approach 3:

The idea is to calculate the position p of last set bit of n and return a number with its (p + 1) bit set.

 
C++ implementation –
 

Download   Run Code

Output:

Next power of 2 is 32

 

Approach 4:

The idea is to set all bits on the right-hand side of the most significant set bit to 1 and and then incrementing the value by 1 so it “rolls over” to the nearest power of two. For instance, consider number 20 (binary 00010100), we convert 00010100 to 00011111. Then we add 1 to it, so that it becomes (00011111 + 1) = 00100000 which is equal to next power of 20.

 
C++ implementation –
 

Download   Run Code

Output:

Next power of 2 is 256

 

How does Right shift and OR operation works?

Let’s take an example of 131, which is 10000011 in binary –

n–; // 10000011 –> 10000010
n |= n >> 1; // 10000010 | 01000001 = 11000011
n |= n >> 2; // 11000011 | 00110000 = 11110011
n |= n >> 4; // 11110011 | 00001111 = 11111111
n |= n >> 8; // … (At this point all bits are 1, so further bitwise-OR
n |= n >> 16; // operations produce no effect)
n++; // 11111111 –> 100000000

There’s one bit in the 9th position, which represents 2^8, 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 0’s, 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.

 
There are several other solution possible for this problem.
 

References:
https://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz