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
Output