Community Problem
Power of Two
Difficulty: Easy
Determine whether a 32-bit signed integer is a power of two using a single bit-AND trick.
Power of Two
Determine whether a 32-bit signed integer is a power of two using a single bit-AND trick.
By CodeSnatch
March 9, 2026
·
Updated May 18, 2026
1,141 views
10
4.3 (14)
Asked at a Cloudflare phone screen as the warm-up that decided whether the rest of the loop happened. The interviewer wanted the bit trick, not Math.log2, and was watching for whether I would correctly reject zero and negatives. Easy to state, easy to fail on n = 0 if you trust the formula too much.
Power of Two
Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two if there exists an integer x such that n == 2^x.
Examples
Example 1:
- Input:
n = 1 - Output:
true - Explanation:
2^0 == 1.
Example 2:
- Input:
n = 16 - Output:
true - Explanation:
2^4 == 16.
Example 3:
- Input:
n = 3 - Output:
false - Explanation:
3is not a power of two; its binary form11has two set bits.
Example 4:
- Input:
n = 0 - Output:
false - Explanation: Zero has no set bits and is not a power of two.
Example 5:
- Input:
n = -16 - Output:
false - Explanation: Powers of two are positive by definition for this problem.
Constraints
-2^31 <= n <= 2^31 - 1.
Follow-up
Could you solve it without loops or recursion? The bit-AND identity n & (n - 1) == 0 runs in constant time and constant space, no iteration needed.
Solution
Hints
Solution Walkthrough
Approach: Bit-AND Identity (O(1) time, O(1) space)
Write a positive power of two in binary: it is exactly one 1 followed by zeros, e.g. 1000. Subtracting 1 flips that 1 to 0 and turns every bit below it to 1, e.g. 0111. The AND of 1000 and 0111 is 0000. For any non-power, the original has at least two set bits; subtracting 1 only flips the lowest set bit, leaving at least one bit shared with the original, so the AND is non-zero.
Key Insight
binary view
8 = 1000
7 = 0111
8 & 7 = 0000 true power of two
12 = 1100
11 = 1011
12 & 11 = 1000 non-zero, not a powerAlgorithm
- If
n <= 0, returnfalse. Powers of two are positive. - Return
(n & (n - 1)) == 0.
Why It Works
A positive integer has exactly one set bit if and only if it is a power of two. The expression n & (n - 1) clears the lowest set bit; the result is zero iff that was the only set bit. Two checks (n > 0 and the AND) cover the entire constraint range.
Complexity
Metric Value
Time O(1)
Space O(1)Pitfalls
- Forgetting
n <= 0. Without the guard,n = 0returnstrue(since0 & -1 == 0), which is wrong. - Using
Math.log2(n) % 1 === 0. Floating-point imprecision makeslog2(2^29)non-integer on some runtimes. The bit trick avoids the whole class of issues. - Treating negatives as valid. In two's complement,
-2^khas many set bits in its 32-bit representation, so the bit trick alone would mis-handle them without then <= 0guard.
Solution Code