# 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 0Hence , 16 is the power of 2But 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 1So 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL