Is This Integer a Power of Two? One Bitwise Operation
Given an integer $x$, determine whether it is a power of $2$ (that is, whether $x = 2^n$ for some integer $n \ge 0$). Find a method that uses $O(1)$ time and no loops, explain why it works, and handle the edge cases $x = 0$ and $x < 0$.
Hints
- Write $x$ in binary. A power of two has exactly one bit set; what does $x - 1$ look like in binary?
- If $x = 2^n$ then $x - 1 = 2^n - 1$ has the $n$ low bits set and the $n$-th bit clear, so $x$ and $x - 1$ share no set bits.
- Test
x & (x - 1) == 0, but first requirex > 0: zero also satisfies the bitwise test and negative numbers must be excluded.
Worked Solution
How to Think About It: Powers of two are the integers whose binary representation contains a single $1$. So the question is really "does $x$ have exactly one set bit?", and there is a classic bit trick that removes the lowest set bit in one operation.
Approach: Show that $x \,\&\, (x - 1)$ clears the lowest set bit, so it is zero if and only if $x$ has at most one set bit; add the guard $x > 0$.
Formal Solution:
*Step 1 -- Binary structure of $x - 1$.* Let $x > 0$ have lowest set bit at position $n$, so $x = (\ldots b\,1\,0\ldots0)_2$ with $n$ trailing zeros. Subtracting $1$ borrows through the trailing zeros: $x - 1 = (\ldots b\,0\,1\ldots1)_2$. All bits above position $n$ are unchanged, bit $n$ becomes $0$, and the $n$ bits below become $1$.
*Step 2 -- Effect of the AND.* Bits above $n$: identical in $x$ and $x - 1$, so they survive. Bit $n$: $1$ in $x$, $0$ in $x - 1$, cleared. Bits below $n$: $0$ in $x$, cleared. Hence $x \,\&\, (x - 1)$ equals $x$ with its lowest set bit removed.
*Step 3 -- Characterization.* The result is $0$ if and only if $x$ had no set bits above its lowest one, i.e. exactly one set bit, i.e. $x = 2^n$. So for $x > 0$: $x$ is a power of two $\iff x \,\&\, (x - 1) = 0$.
*Step 4 -- Edge cases.* $x = 0$: $0 \,\&\, (-1) = 0$, but $0$ is not a power of two, so the test must be x > 0 and (x & (x - 1)) == 0. Negative $x$: in two's complement $-2^n$ is not a power of two by the usual definition, and the guard excludes it (note $-2^{31}$ in 32-bit arithmetic would otherwise pass the bitwise test, since INT_MIN & (INT_MIN - 1) wraps to INT_MIN & INT_MAX = 0). Also x - 1 underflows for INT_MIN, another reason to check the sign first.
*Step 5 -- Alternatives.* x & -x isolates the lowest set bit, so x > 0 and (x & -x) == x is equivalent. A population count (bin(x).count('1') == 1 in Python, __builtin_popcount(x) == 1 in GCC) also works. Any loop over bits is $O(\log x)$ instead of $O(1)$.
```python def is_power_of_two(x: int) -> bool: return x > 0 and (x & (x - 1)) == 0
assert [is_power_of_two(v) for v in (0, 1, 2, 3, 4, 6, 8, 1024, 1025, -4)] == \ [False, True, True, False, True, False, True, True, False, False] ```
The function was checked against a popcount reference for every integer from $-5$ to $10^5$ and for $2^{62}$ and $2^{62} + 1$.
Answer: $x$ is a power of two if and only if $x > 0$ and $x \,\&\, (x - 1) = 0$, because $2^n$ has a single set bit while $2^n - 1$ has exactly the $n$ bits below it set, so the two share no bits; any other positive integer keeps its higher bits after clearing the lowest one. $O(1)$ time; guard against $x = 0$ and negatives.
Intuition
Subtracting one from a binary number flips its lowest set bit to zero and turns every bit below it into one, so x & (x - 1) simply clears the lowest set bit. The result is zero exactly when there was only one set bit, i.e. when $x$ is a power of two. This one-liner is a favourite because it tests whether the candidate knows how integers are represented; the same idea underlies Brian Kernighan's population count, Fenwick trees, and checking whether a buffer size is a power of two for fast modular indexing with a mask.