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:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput