Power of Two
Determine whether an integer is a power of two using a bitwise trick, not repeated division.
Open on LeetCode ↗Intuition
The trap is forgetting that zero and negative numbers are not powers of two, and letting the classic bit trick silently accept zero anyway. n & (n-1) == 0 is the standard test: a power of two has exactly one set bit, and subtracting 1 flips that bit off and turns every bit below it on, so ANDing the two clears everything to zero. The problem is that 0 & -1 also equals 0 in two's complement, so the bit trick alone says 'yes' for zero even though zero is not a power of two. The fix is to guard n > 0 before ever touching the bit trick -- once positivity is confirmed, the AND trick is airtight because a positive integer's binary representation has no ambiguity about its highest bit.
n & (n - 1) clears the lowest set bit. A power of two has exactly one set bit, so clearing it leaves zero — one operation, no loop, no division. The same identity underpins counting set bits (Brian Kernighan's algorithm) and is worth recognising on sight.
Approach
Guard non-positive values first
If n <= 0, return False immediately. This handles zero and all negative numbers before the bit trick has a chance to misfire on them.
Apply the single-set-bit test
For n > 0, compute n & (n - 1). A power of two in binary looks like a single 1 followed by zeros; subtracting 1 turns that pattern into all 1s below the original bit and clears the original bit itself, so the AND of the two is 0 exactly when n has one set bit.
Return the comparison
Return whether n & (n - 1) equals 0. Combined with the earlier positivity guard, this is a full, O(1), constant-space test with no loops or divisions.
Solution & live demo
Common pitfalls
Forgetting the positivity guard
return (n & (n - 1)) == 0
if n <= 0: return False return (n & (n - 1)) == 0
0 & -1 is 0, so zero reports as a power of two. Negative numbers can also slip through in two's-complement representations. Powers of two are strictly positive, and the guard must come first.
Looping with repeated division
while n % 2 == 0: n //= 2 return n == 1
return (n & (n - 1)) == 0
Correct but O(log n) with a division each round. The bit trick answers in a single operation — and demonstrating that you know it is the point of the question.
Using a floating-point logarithm
return math.log2(n).is_integer()
return (n & (n - 1)) == 0
Floating point rounding makes large values like 2^29 occasionally test as non-integral, or a near-miss test as exact. Integer bit operations have no such failure mode.
Edge cases
guarded out by n > 0 check, returns False
guarded out by n > 0 check, returns False
n & (n-1) = 1 & 0 = 0, returns True
bit trick works identically regardless of magnitude, no overflow in Python