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

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 27 28 29 30 |
#include <iostream> #include <cmath> using namespace std; // compute power of two greater than or equal to n unsigned nextPowerOf2(unsigned n) { // decrement n (to handle the case when n itself // is a power of 2) n = n - 1; // 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 n) // return next power of 2 return n << 1; } // main function int main() { unsigned n = 127; cout << "Next power of 2 is " << nextPowerOf2(n); return 0; } |

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

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <cmath> using namespace std; // compute power of two greater than or equal to n unsigned nextPowerOf2(unsigned n) { // decrement n (to handle the case when n itself // is a power of 2) n = n - 1; // initialize result by 2 int k = 2; // double k and divide n in half till it becomes 0 while (n >>= 1) k = k << 1; // double k return k; } /* unsigned nextPowerOf2(unsigned n) { int k = 1; while (k < n) k = k << 1; return k; } */ // main function int main() { unsigned n = 127; cout << "Next power of 2 is " << nextPowerOf2(n); return 0; } |

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

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 27 |
#include <iostream> #include <cmath> using namespace std; // compute power of two greater than or equal to n unsigned nextPowerOf2(unsigned n) { // decrement n (to handle the case when n itself // is a power of 2) n = n - 1; // calculate position of last set bit of n int lg = log2(n); // next power of two will have bit set at position (lg + 1) return 1U << lg + 1; } // main function int main() { unsigned n = 20; cout << "Next power of 2 is " << nextPowerOf2(n); return 0; } |

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

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 27 28 29 |
#include <iostream> using namespace std; // compute power of two greater than or equal to n unsigned nextPowerOf2(unsigned n) { // decrement n (to handle the case when n itself is a power of 2) n--; // Set all bits after the last set bit n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // increment n and return return ++n; } // main function int main() { unsigned n = 131; cout << "Next power of 2 is " << nextPowerOf2(n); return 0; } |

`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