Round up to the next highest power of 2
Given a positive number n, find the next highest power of 2. If n itself is a power of 2, return n.
For example,
Output: 32
Input: n = 16
Output: 16
Approach 1
The idea is to unset the rightmost bit of n until only one bit is left, which will be the last set bit of the given number. To handle the case when n is the power of 2, initially decrement n by 1. Note that this operation will not impact output as we are only concerned about the last set bit of n.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 findNextPowerOf2(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; } int main() { unsigned n = 127; cout << "The next power of 2 is " << findNextPowerOf2(n); return 0; } |
Output:
The next power of 2 is 128
Java
|
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 |
class Main { // Compute power of two greater than or equal to `n` public static int findNextPowerOf2(int n) { // decrement `n` (to handle cases when `n` itself // is a power of 2) n = n - 1; // do till only one bit is left while ((n & n - 1) != 0) { 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; } public static void main(String[] args) { int n = 127; System.out.println("The next power of 2 is " + findNextPowerOf2(n)); } } |
Output:
The next power of 2 is 128
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Compute power of two greater than or equal to `n` def findNextPowerOf2(n): # decrement `n` (to handle cases 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 if __name__ == '__main__': n = 127 print('The next power of 2 is', findNextPowerOf2(n)) |
Output:
The next power of 2 is 128
Approach 2
The idea is to decrement n by 1 (to handle the case when n itself is the power of 2) and run a loop by initializing the result by 2. We double the result value at each iteration of the loop and divide n in half and continue the loop till n becomes 0.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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 41 |
#include <iostream> #include <cmath> using namespace std; // Compute power of two greater than or equal to `n` unsigned findNextPowerOf2(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 findNextPowerOf2(unsigned n) { int k = 1; while (k < n) { k = k << 1; } return k; } */ int main() { unsigned n = 127; cout << "The next power of 2 is " << findNextPowerOf2(n); return 0; } |
Output:
The next power of 2 is 128
Java
|
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 |
class Main { // Compute power of two greater than or equal to `n` public static int findNextPowerOf2(int n) { // decrement `n` (to handle cases 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) != 0) { k = k << 1; // double `k` } return k; } /*public static int findNextPowerOf2(int n) { int k = 1; while (k < n) { k = k << 1; } return k; }*/ public static void main(String[] args) { int n = 127; System.out.println("The next power of 2 is " + findNextPowerOf2(n)); } } |
Output:
The next power of 2 is 128
Python
Approach 3
The idea is to calculate position p of the last set bit of n and return a number with its p+1 bit set. Following is the C++, Java, and Python program that demonstrates it:
C++
|
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 greater than or equal to `n` unsigned findNextPowerOf2(unsigned n) { // decrement `n` (to handle the case when `n` itself // is a power of 2) n = n - 1; // calculate the position of the last set bit of `n` int lg = log2(n); // next power of two will have a bit set at position `lg+1`. return 1U << lg + 1; } int main() { unsigned n = 20; cout << "The next power of 2 is " << findNextPowerOf2(n); return 0; } |
Output:
The next power of 2 is 32
Java
|
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 |
class Main { public static int log(int x, int base) { return (int) (Math.log(x) / Math.log(base)); } // Compute power of two greater than or equal to `n` public static int findNextPowerOf2(int n) { // decrement `n` (to handle the case when `n` itself // is a power of 2) n = n - 1; // calculate the position of the last set bit of `n` int lg = log(n, 2); // next power of two will have a bit set at position `lg+1`. return 1 << lg + 1; } public static void main(String[] args) { int n = 20; System.out.println("The next power of 2 is " + findNextPowerOf2(n)); } } |
Output:
The next power of 2 is 32
Python
|
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 |
from math import log def log2(x, base): return int(log(x) / log(base)) # Compute power of two greater than or equal to `n` def findNextPowerOf2(n): # decrement `n` (to handle the case when `n` itself # is a power of 2) n = n - 1 # calculate the position of the last set bit of `n` lg = log2(n, 2) # next power of two will have a bit set at position `lg+1`. return 1 << lg + 1 if __name__ == '__main__': n = 20 print('The next power of 2 is', findNextPowerOf2(n)) |
Output:
The 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 then increment the value by 1 to “rollover” to two’s nearest power. For instance, consider number 20. We convert its binary representation 00010100 to 00011111 and add 1 to it, which results in the next power of 20. i.e., (00011111 + 1) = 00100000.
This approach is demonstrated below in C++, Java, and Python:
C++
|
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 |
#include <iostream> using namespace std; // Compute power of two greater than or equal to `n` unsigned findNextPowerOf2(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; } int main() { unsigned n = 131; cout << "The next power of 2 is " << findNextPowerOf2(n); return 0; } |
Output:
The next power of 2 is 256
Java
|
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 |
class Main { // Compute the next highest power of 2 of a 32–bit number `n` public static int findNextPowerOf2(int n) { // decrement `n` (to handle cases 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; } public static void main(String[] args) { int n = 131; System.out.println("The next power of 2 is " + findNextPowerOf2(n)); } } |
Output:
The next power of 2 is 256
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Compute the next highest power of 2 of a 32–bit number `n` def findNextPowerOf2(n): # decrement `n` (to handle cases when `n` itself is a power of 2) n = n - 1 # 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 + 1 if __name__ == '__main__': n = 131 print('The next power of 2 is', findNextPowerOf2(n)) |
Output:
The next power of 2 is 256
How does right shift and bitwise OR operation works?
Let’s take an example of 131, which is 10000011 in binary:
n--; // 10000011 ——> 10000010n |= n >> 1; // 10000010 | 01000001 = 11000011n |= n >> 2; // 11000011 | 00110000 = 11110011n |= n >> 4; // 11110011 | 00001111 = 11111111n |= n >> 8; // … (At this point, all bits are 1, so further bitwise ORn |= n >> 16; // operations produce no effect)n++; // 11111111 ——> 100000000
There’s one bit in the 9th position, which represents 28, which is indeed the next largest power of 2. Each of the shifts overlaps all the existing 1 bits in the number with some previously untouched 0’s, eventually producing the total number of 1 bit equal to the total number of bits in the original number. Adding one to that value produces a new power of 2.
There are several other solutions possible for this problem.
References: https://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)