Round up to the previous power of 2

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

 

For example,

Input: n = 20
Output: 16
 

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 and a previous power of 2.

 
C++ implementation –
 

Download   Run Code

Output:

Previous power of 2 is 64

 

Approach 2:

The idea is to run a loop by initializing the result by 1. 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:

Previous power of 2 is 64

 

Approach 3:

The idea is to calculate the position p of last set bit of n and return a number with its p’th bit set. In other words, we drop all set bits from n except its last set bit.

 
C++ implementation –
 

Download   Run Code

Output:

Previous 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 drop all bits but the last set bit from n so that it becomes equal to the previous power of two. For instance, consider number 20 (binary 00010100), we convert 00010100 to 00011111. Then we drop all set bits except the last one so that it becomes 00010000 which is equal to 16, the previous power of 20.

 
C++ implementation –
 

Download   Run Code

Output:

Previous power of 2 is 256

 

How does Right shift and Bitwise OR operation works?

Let’s take an example of 130, which is 10000010 in binary –

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 – (n >> 1); // 11111111 – 01111111 –> 10000000

There’s one bit in the 8th position, which represents 2^7, which is indeed the previous 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. We finally drop all bits except the last set bit.

 
There are several other solution possible for this problem.
 

References: Hacker’s Delight

 
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 🙂