Power of Two asks a tiny question with a beautiful one-line answer. It is the classic warm-up for bit manipulation: once you see numbers as their binary shape, the trick n & (n - 1) becomes obvious and shows up everywhere.
Problem. Given an integer n, return true if it is a power of two — that is, if n == 2^x
for some non-negative integer x — and false otherwise.
Example: n = 16 → true (because 16 = 2^4). n = 18 → false (it sits between 2^4 and 2^5).
The slow way first
The obvious idea: keep dividing by 2. While n is even, halve it; at the end, check whether you landed exactly on 1. That works and is O(log n), but it is a loop with a remainder check on every step — more code, more chances for an off-by-one, and it needs a special case for n <= 0.
The question to ask: what makes a power of two special in binary? Write a few out and the pattern jumps out — every power of two is a single 1 followed by zeros.
The idea: exactly one set bit
In binary, the powers of two are 1, 10, 100, 1000, ... — each is exactly one 1-bit with zeros everywhere else. So "is n a power of two?" becomes "does n have exactly one set bit?"
There is a famous one-instruction way to test that. Subtracting 1 from a number flips its lowest set bit to 0 and turns every bit below it into 1. So n & (n - 1) clears the lowest set bit. If n had only that one bit, the AND wipes it out and the result is 0. If n had more bits, at least one survives and the result is non-zero.
The one guard you must not forget: require n > 0 first. For n = 0, n & (n - 1) is also 0, which would wrongly say "power of two." Zero and negative numbers are never powers of two.
Walk through it
Step through the animation. For n = 16 = 00010000 there is a single 1 at bit 4; n - 1 = 15 = 00001111 flips that bit and lights up everything below it, so the AND is all zeros — True. Then watch the contrast: n = 18 = 00010010 has two 1-bits, so n & (n - 1) clears only the lowest and leaves bit 4 standing, giving 16 — not zero, so False.
Pseudocode
if n <= 0:
return False # 0 and negatives are never powers of two
return (n & (n - 1)) == 0 # exactly one set bit -> AND wipes it to 0The Python solution
def is_power_of_two(n):
# a power of two has exactly one set bit
# n & (n - 1) clears that lowest set bit
return n > 0 and (n & (n - 1)) == 0- A power of two looks like a single
1in binary, so the whole test is just "doesnhave one set bit?" n - 1flips the lowest set bit to0and sets every lower bit to1.n & (n - 1)therefore clears the lowest set bit; if that empties the number, only one bit was set.n > 0is the essential guard — without it,n = 0would slip through (0 & -1 == 0).- Python short-circuits
and, so the bit test only runs oncenis known to be positive.
Complexity
| Case | Time | Notes |
|---|---|---|
| Divide-by-2 loop | O(log n) (fast) | halve until you reach 1 |
| Bit trick (this solution) | O(1) (fast) | one AND, one compare |
O(1) (fast)The bit version is a couple of machine instructions — no loop at all. That single move, clear the lowest set bit with n & (n - 1), is one of the most reused tricks in the field.
When this pattern shows up
Any time a problem cares about how many bits are set, reach for n & (n - 1). It clears the lowest
set bit in one step, so it powers "count set bits" (Brian Kernighan), "is this a power of two,"
and "single set bit" checks. Memorize what n - 1 does to the binary shape and these become one-liners.
Do not forget the n > 0 guard. 0 & (0 - 1) is 0, so a naive (n & (n - 1)) == 0 would call 0 a
power of two. Negative numbers fail for the same reason — rule them out first.
Practice
For n = 18 = 00010010, what is n & (n - 1), and what does that tell you?
1. What binary shape does every power of two have?
2. What does n & (n - 1) do to a binary number?
3. Why is the n > 0 guard necessary?
4. What is the time complexity of the bit-trick solution?