C++ program to check if number is power of 2 using Bitwise operator

In this article, we are going to learn how to check whether a given number is the power of 2 or not using bitwise operator?
Submitted by Yash Khandelwal, on April 27, 2019

Given a number and we have to check whether it is power of 2 or not.

An obvious approach is to divide the number by 2 until the number will not get 0 or 1. But This Algorithm has the problem of Time complexity. This algorithm takes the O(log(n)) complexity to solve such a simple problem.

So how can we improve this?, Can this be solved in order of O(1) complexity?

The answer to this is "yes", with the help of the bitwise operator.

But, before this, we have to know about a simple property of binary number which is "the power of 2 having only one set bit in their Binary representation".

For example,

     2 =    0001
     4 =    0100
     8 =    1000
    16 =   10000
    32 =  100000
    64 = 1000000
    so on..

Now, let be more precise about this,

If we subtract 1 from the power of 2 what we get is 1s at all the places from the end of the binary number till we will not get 1 set bit. And, if we apply Bitwise AND operator we should only get zeros.

This will get clearer with this example:

    Let the no n =16

    Binary representation of 16 is 
        16  =  0 0 0 1 0 0 0 0
        16-1=  0 0 0 0 1 1 1 1
        ----------------------------
    Now 16 AND 15=  0 0 0 0 0 0 0 0

    Hence , 16 is the power of 2

    But what in case if it is not:

    Let the no n=15
        15 =  0 0 0 0 1 1 1 1    
        14 =  0 0 0 0 1 1 1 0
        ----------------------------
    15 AND 14=  0 0 0 0 1 1 1 1

    So 15 is not the power of 2.

Now, this can be implemented with order of complexity 1

    if (n & (n-1) == 0) return true;

Example:

    INPUT:
    n = 4
    n-1 = 3 
    n & n-1 = 0
    (AND of 100 with 011) 
    Output= TRUE

    INPUT:
    n = 9
    n-1 = 8
    n & n-1 = 9 
    (AND of 1001 with 1000)
    Output= FALSE

    INPUT:
    n = 15
    n-1 = 14 
    n & n-1 = 14
    (AND of 01111 with 01110)
    Output=FALSE

    INPUT:
    n = 16
    n-1 = 15 
    n & n-1 = 0 
    (AND of 10000 with 01111)
    Output= TRUE

C++ implementation

// program to find that the number is power of 2
#include<iostream>
using namespace std;

int main()
{
	// declaring the array n
	int n[]={4,9,15,16,20,22,25,32,45,64,72,80,100,128,256};
	int i;
	
	for(i=0;i<15;i++)
	{
		cout<< n[i] << " is power of 2 : ";
		// use of bitwise AND (&) operator
		if((n[i]& (n[i]-1))==0) 
			cout<<"True"<<endl;
		else
			cout<<"False"<<endl;
	}
	
	return 0;	
}

Output

4 is power of 2 : True 
9 is power of 2 : False
15 is power of 2 : False 
16 is power of 2 : True
20 is power of 2 : False 
22 is power of 2 : False 
25 is power of 2 : False 
32 is power of 2 : True
45 is power of 2 : False 
64 is power of 2 : True
72 is power of 2 : False 
80 is power of 2 : False 
100 is power of 2 : False
128 is power of 2 : True 
256 is power of 2 : True