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

Program:Output