# 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.
```