**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++ implementationOutput