Check if a number is a power of 2 with a single bitwise operation
Given a positive integer n, you are asked to find out if it’s a power of 2. It’s possible to do that with a single bitwise operation. If we consider the bitwise representation of a number that’s a power of 2, then it has a single 1 in the representation and the rest are 0s.
number | Binary representation |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Random Number | Binary representation |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
This can be seen from the definition of binary representation. Every position with a 1 corresponds to the addition of that power of 2 (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). So, having a single 1 in the binary representation of a number means that there are no other powers of 2 in the sum other than that one. So, the problem becomes checking if there is only a single 1 in the binary representation of n.
An easy way of doing that is by doing a bitwise & of n and n-1. If the result is 0 ⇒ it’s a power of 2.
For any number that’s not a power of 2, the result of n & (n-1) will be different from 0:
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
Yet, for the powers of 2, it’s always 0:
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
Input
The first line of the input contains a single integer n (2 ≤ n ≤ ).
Output
The program should print Yes if n is a power of 2 and No otherwise.
Examples
Input | Output |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB