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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of