211. Power of Two
Given an integer n, decide whether it is a power of two: is there some integer x >= 0 with n = 2^x? Return true if so, false otherwise.
A few cases people forget: 1 is a power of two (it is 2^0), while 0 and every negative number are not.
A loop of divisions works — but there is a famous one-line bit trick. Can you find it, and explain why it works?
Example 1:
Input: n = 1
Output: true
Explanation: 1 = 2^0, so it counts.
Example 2:
Input: n = 16
Output: true
Explanation: 16 = 2^4.
Example 3:
Input: n = 3
Output: false
Explanation: 3 sits between 2^1 and 2^2 — no exponent produces it.
Constraints:
- -2³¹ ≤ n ≤ 2³¹ - 1
Hints:
Rule out n <= 0 first: no power of two is zero or negative. After that, a power of two must divide down to 1 by repeatedly halving with no remainder.
Write some powers of two in binary: 1, 10, 100, 1000... exactly one bit is set. What does subtracting 1 do to a number like that?
For n = 2^x, n - 1 flips that single set bit and sets all the bits below it, so n & (n - 1) == 0. For any positive n with two or more set bits, the highest bit survives the AND. So the test is: n > 0 and n & (n - 1) == 0.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 1
Expected output: true