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

#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; }

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

Finding previous power of 2

All Answers

C++ programs on various topics

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now