Power of Two: Bit Manipulation One-Liner

LeetCode Power of Two (Problem 231) asks: given an integer n, return true if it is a power of two, and false otherwise.

A number is a power of two if there exists some integer k such that n == 2^k. For example, 1, 2, 4, 8, and 16 are all powers of two. Numbers like 3, 6, and 0 are not.

You could loop and keep dividing by 2, but there is a one-liner using bit manipulation that solves it in constant time. The key observation is that every power of two has exactly one bit set in its binary representation.

The approach

Why do powers of two have exactly one set bit? Think about what 2^k means in binary. 2^0 is 1, 2^1 is 10, 2^2 is 100, and so on. Each power of two simply places a single 1 in a different bit position. No other positive integers share this property.

Now consider the expression n & (n - 1). This is a classic bit trick that clears the lowest set bit of n. When you subtract 1 from a number, all the bits below the lowest set bit flip (the lowest set bit becomes 0, and all the zeros below it become 1s). ANDing n with n - 1 zeros out that lowest set bit and everything below it.

If n is a power of two, it has exactly one set bit. Clearing that one bit with n & (n - 1) produces 0. If n is not a power of two, it has multiple set bits, so clearing one still leaves others behind, and the result is nonzero.

You also need to check that n > 0, since zero and negative numbers are never powers of two.

The solution

def isPowerOfTwo(n: int) -> bool:
    return n > 0 and n & (n - 1) == 0

1. Check n > 0: Zero has no set bits, so n & (n - 1) would be 0, but zero is not a power of two. Negative numbers are never powers of two either.
2. Compute n & (n - 1): This clears the lowest set bit of n.
3. Compare to 0: If the result is 0, then n had exactly one set bit, which means it is a power of two.
4. Short-circuit evaluation: Python evaluates n > 0 first. If n is zero or negative, the second condition is never checked.

Step-by-step walkthrough

Let's trace through two examples. First with n = 16 (a power of two), then with n = 6 (not a power of two). Watch how the bit trick distinguishes them.

For n = 16, the single set bit in 10000 lines up perfectly with all zeros in 01111, so the AND produces 00000. For n = 6, the upper set bit survives the AND because it appears in both 0110 and 0101. That leftover bit tells you 6 is not a power of two.

Complexity analysis

The solution uses one subtraction, one AND, and two comparisons. No loops, no recursion, no additional memory. Everything runs in constant time regardless of the size of n.

Building blocks

This problem builds on three reusable techniques that CodeBricks drills independently:

The n & (n-1) trick

This clears the lowest set bit of any integer. It is the single most useful bit manipulation primitive. It appears in counting set bits, checking powers of two, and isolating specific bit patterns.

n &= n - 1

Single-bit property of powers of two

Recognizing that 2^k always has exactly one bit set in binary. This connects the abstract math (powers of two) to a concrete bit pattern you can test mechanically.

Guard conditions for edge cases

Checking n > 0 before applying bit logic. Many bit manipulation problems require a boundary check to handle zero, negatives, or overflow before the core trick applies.

Edge cases

n = 0: Zero has no set bits. 0 & (-1) would be 0, which would incorrectly pass the bit check. The n > 0 guard catches this. Return false.

n = 1: Binary 1. This is 2^0, a valid power of two. 1 & 0 = 0. Return true.

n = negative (e.g., n = -8): Negative numbers are never powers of two in standard integer math. The n > 0 guard immediately returns false.

Large power of two (e.g., n = 2^30 = 1073741824): A single bit set at a high position. n & (n - 1) still produces 0. Return true.

Integer.MIN_VALUE (e.g., -2147483648 in 32-bit): In languages like Java, this value has a single bit set (the sign bit), so n & (n - 1) would be 0. But it is negative, so the n > 0 check correctly returns false. Always guard against negative inputs.

n = 3: Binary 11. Two bits set. 3 & 2 = 10 & 11 = 10 = 2, which is not 0. Return false.

From understanding to recall

Power of Two is one of the simplest LeetCode problems once you know the trick. But knowing it exists and recalling it under pressure are two different things. In an interview, you need n > 0 and n & (n - 1) == 0 to flow out without hesitation. You need to explain why it works without pausing to re-derive the bit math.

Spaced repetition locks this in. You type the solution from scratch today, then again in a few days, then a week later. Each time, the retrieval gets faster. Eventually the pattern is automatic, and you can focus on the harder parts of whatever problem uses it as a building block.

Related posts

• Number of 1 Bits - Uses the same n & (n-1) trick in a loop to count set bits. Power of Two is essentially asking "does this loop run exactly once?"
• Reverse Bits - Another bit-by-bit manipulation problem on 32-bit integers. Builds the same comfort with shifts and masks that makes Power of Two feel natural.
• Single Number - Uses XOR bit trick to find the lone element in an array. A different bitwise primitive, but the same category of "one clever operation solves the whole problem."