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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <cmath> using namespace std; // compute power of two less than or equal to n unsigned previousPowerOf2(unsigned n) { // do till only one bit is left while (n & n - 1) n = n & n - 1; // unset rightmost bit // n is now a power of two (less than or equal to n) return n; } // main function int main() { unsigned n = 127; cout << "Previous power of 2 is " << previousPowerOf2(n); return 0; } |

`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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <cmath> using namespace std; // compute power of two less than or equal to n unsigned previousPowerOf2(unsigned n) { // initialize result by 1 int k = 1; // double k and divide n in half till it becomes 0 while (n >>= 1) k = k << 1; // double k return k; } // main function int main() { unsigned n = 127; cout << "Previous power of 2 is " << previousPowerOf2(n); return 0; } |

`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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <cmath> using namespace std; // compute power of two less than or equal to n unsigned previousPowerOf2(unsigned n) { // drop all set bits from n except its last set bit return 1U << (int)log2(n); } // main function int main() { unsigned n = 20; cout << "Previous power of 2 is " << previousPowerOf2(n); return 0; } |

`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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; // compute power of two less than or equal to n unsigned previousPowerOf2(unsigned n) { // Set all bits after the last set bit n = n | (n >> 1); n = n | (n >> 2); n = n | (n >> 4); n = n | (n >> 8); n = n | (n >> 16); // drop all bits but the last set bit from n return n - (n >> 1); } // main function int main() { unsigned n = 131; cout << "Previous power of 2 is " << previousPowerOf2(n); return 0; } |

`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 🙂

## Leave a Reply