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