# 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 `0`

s.2^n 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

💡

**Intuition**When considering the numbers

`n`

and `n-1`

, the most significant bit of those two is preserved only when the binary representation of `n`

has other 1s other than the most significant bit. If `n`

is a power of 2 ⇒ the binary representation has only a single 1, and thus when subtracting 1, `n-1`

loses the most significant bit (it becomes 0 and the rest of the bits turn to 1).
For other numbers (6, 67, 144, etc.) their binary representations contain several 1s. Therefore, when subtracting 1 from them, they don’t lose their most significant bits. 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: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB