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

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;