Home » C++ programs » C++ Bit manipulation programs

# Find next and previous power of two of a given number in C++

Here, we are going to learn **how to find the next and previous power of two of a given number using C++ program**?

Submitted by Hritik Raj, on June 24, 2018

**Problem statement:**

Find Next and previous power of two of a given number

**Next power of two**

Example(1): input: 22 output: 32 ( as 32 is 2^5) Example(2): input: 54 output: 64 (as 64 is 2^6)

**Previous power of two**

Example(1): input: 22 output: 16 Example(2): input: 54 output: 32

We can solve this problem using bit manipulation easily.

Just have a look on the binary representation of the number which is a power of 2.

power of 2 Binary Representation 1 1 2 10 4 100 8 1000 16 10000 32 100000 64 1000000 128 10000000

As we can see every number have only their left most bit set (i.e 1) and rest are unset (i.e 0).

### Finding previous power of 2

If we somehow, can unset all bits except the left most bit in a binary representation of number we will get previous power of two of the given number.

**Example:**

Number Binary representation previous power of two 7 111 100 (i,e 4) 25 11001 10000 (i.e 16) 95 1011111 1000000 (i,e 64)

We will use Bitwise AND ( & ) operation to clear bits.

Here is Algorithm to get previous power of 2 of n,

step 1: n = n & n-1 step 2: if n is power of two , n is our desired result,go to step 3. else go to step 1. step 3: print n and stop

**Explanation:**

let n = 27 ( 11011 in binary) n-1 = 26 ( 11010 in binary) n&n-1 = 26 as 26 is not a power of 2 so we will repeat above step again new n = 26 n = 26 ( 11010 in binary) n-1 = 25 ( 11001 in binary) n&n-1 = 24 ( 11000 in binary) as 24 is not a power of 2 so we will repeat above step again new n=24 n = 24 ( 11000 in binary) n-1 = 23 ( 10111 in binary) n&n-1 = 16 ( 10000 in binary) as 16 is a power of 2 so this is our answer

### Finding next power of Two

To get next power of two, all we have to do is to find a binary number greater than the given number having only left most bit set.

We can use left shift operator ( << )to generate a number having only its left most bit set.

Left shift operation example:

1 << 5 This means that shift 1 left by 5 place 1 in binary is represented as 1 so after shifting 1 by 5 place left, output will be 100000 ( i.e 32 in decimal) 5 << 2 This means that shift 5 left by 2 place 5 in binary is represented as 101 so after shifting it by 2 place to left, output will be 10100 ( i.e 20 in decimal)

**Note:** In each shift right most bit will be set to 0;

**Program:**

#include<bits/stdc++.h> using namespace std; long int nextPowerOfTwo ( int n ) { // Result is intialized as 1 long int value = 1; // The following while loop will run until we // get a number greater than n while(value<=n) { // value will be left shifted by 1 place in each iteration value=value << 1; } return value ; } int previousPowerOfTwo(int n ) { // If n is already a power of two, we can simply shift it right // by 1 place and get the previous power of 2 // (n&n-1) will be 0 if n is power of two ( for n > = 2 ) // (n&&!(n&(n-1))) condition will take care of n < 2; if((n&&!(n&(n-1)))==1) { return (n>>1); } // This while loop will run until we get a number which is a power of 2 while(n&n-1) { // Each time we are performing Bit wise And ( & )operation to clear bits n=n&n-1; } return n ; } int main() { int n; cout << "Enter Number\n"; cin >> n; long int num=nextPowerOfTwo(n); cout << "Next power of two : " << num ; cout << "\n\nEnter Number\n"; cin >> n; num=previousPowerOfTwo(n); cout << "Previous power of two : " << num ; return 0; }

**Output**

Enter Number 34 Next power of two : 64 Enter Number 34 Previous power of two : 32 Process returned 0 (0x0) execution time : 7.681 s Press any key to continue.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions