Round up to the previous power of 2
Given a positive number n, find the previous power of 2. If n itself is a power of 2, return n.
For example,
Output: 16
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 and a previous power of 2. 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 |
#include <iostream> #include <cmath> using namespace std; // Compute a power of two less than or equal to `n` unsigned findPreviousPowerOf2(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; } int main() { unsigned n = 127; cout << "The previous power of 2 is " << findPreviousPowerOf2(n); return 0; } |
Output:
The previous power of 2 is 64
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Main { // Compute a power of two less than or equal to `n` public static int findPreviousPowerOf2(int n) { // 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 or equal to `n`) return n; } public static void main(String[] args) { int n = 128; System.out.println("The previous power of 2 is " + findPreviousPowerOf2(n)); } } |
Output:
The previous power of 2 is 64
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Compute a power of two less than or equal to `n` def findPreviousPowerOf2(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 if __name__ == '__main__': n = 128 print('The previous power of 2 is', findPreviousPowerOf2(n)) |
Output:
The previous power of 2 is 64
Approach 2
The idea is to run a loop by initializing the result by 1. We double the result value at each iteration of the loop and divide n in half and continue the loop till n becomes 0.
Following is the implementation in C++, Java, and Python based on the above 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 |
#include <iostream> #include <cmath> using namespace std; // Compute a power of two less than or equal to `n` unsigned findPreviousPowerOf2(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; } int main() { unsigned n = 127; cout << "The previous power of 2 is " << findPreviousPowerOf2(n); return 0; } |
Output:
The previous power of 2 is 64
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Main { // Compute a power of two less than or equal to `n` public static int findPreviousPowerOf2(int n) { // initialize result by 1 int k = 1; // double `k` and divide `n` in half till it becomes 0 while ((n >>= 1) != 0) { k = k << 1; // double `k` } return k; } public static void main(String[] args) { int n = 127; System.out.println("The previous power of 2 is " + findPreviousPowerOf2(n)); } } |
Output:
The previous power of 2 is 64
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Compute a power of two less than or equal to `n` def findPreviousPowerOf2(n): # initialize result by 1 k = 1 # `k` and divide `n` in half till it becomes 0 while n: k = k << 1 # k n >>= 1 return k >> 1 if __name__ == '__main__': n = 127 print('The previous power of 2 is', findPreviousPowerOf2(n)) |
Output:
The previous power of 2 is 64
Approach 3
The idea is to calculate the position p of the last set bit of n and return a number with its p'th bit set. In other words, drop all set bits from n except its last set bit.
The implementation can be seen 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 |
#include <iostream> #include <cmath> using namespace std; // Compute a power of two less than or equal to `n` unsigned findPreviousPowerOf2(unsigned n) { // drop all set bits from `n` except its last set bit return 1U << (int)log2(n); } int main() { unsigned n = 20; cout << "The previous power of 2 is " << findPreviousPowerOf2(n); return 0; } |
Output:
The previous power of 2 is 16
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Main { public static int log(int x, int base) { return (int) (Math.log(x) / Math.log(base)); } // Compute a power of two less than or equal to `n` public static int findPreviousPowerOf2(int n) { // drop all set bits from `n` except its last set bit return 1 << log(n, 2); } public static void main(String[] args) { int n = 20; System.out.println("The previous power of 2 is " + findPreviousPowerOf2(n)); } } |
Output:
The previous power of 2 is 16
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
from math import log def log2(x, base): return int(log(x) // log(base)) # Compute a power of two less than or equal to `n` def findPreviousPowerOf2(n): # drop all set bits from `n` except its last set bit return 1 << log2(n, 2) if __name__ == '__main__': n = 20 print('The previous power of 2 is', findPreviousPowerOf2(n)) |
Output:
The previous power of 2 is 16
Approach 4
The idea is to set all bits on the right-hand side of the most significant set bit to 1 and then drop all but the last set bit from n so that it becomes equal to the previous power of two. For instance, consider number 20. We convert its binary representation 00010100 to 00011111. Then drop all set bits except the last one to become 00010000, which is equal to 16 (the previous power of 20).
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 |
#include <iostream> using namespace std; // Compute a power of two less than or equal to `n` unsigned findPreviousPowerOf2(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 but the last set bit from `n` return n - (n >> 1); } int main() { unsigned n = 131; cout << "The previous power of 2 is " << findPreviousPowerOf2(n); return 0; } |
Output:
The previous 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 |
class Main { // Compute a power of two less than or equal to `n` public static int findPreviousPowerOf2(int 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 but the last set bit from `n` return n - (n >> 1); } public static void main(String[] args) { int n = 131; System.out.println("The previous power of 2 is " + findPreviousPowerOf2(n)); } } |
Output:
The previous 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 |
# Compute a power of two less than or equal to `n` def findPreviousPowerOf2(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 but the last set bit from `n` return n - (n >> 1) if __name__ == '__main__': n = 131 print('The previous power of 2 is', findPreviousPowerOf2(n)) |
Output:
The previous power of 2 is 128
How does Right shift and bitwise OR operation works?
Let’s take an example of 130, which is 10000010 in binary:
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 27, which is indeed the previous 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. We finally drop all bits except the last set bit.
There are several other solutions possible for this problem.
References: Hacker’s Delight
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 :)