Power of Two LeetCode Solution: The One Bit Trick You Need

Power of Two (#231) is one of those rare LeetCode problems where the optimal solution fits in a single line of code. But that one line encodes a bit manipulation technique — n & (n-1) — that shows up everywhere, from counting set bits to Hamming distance to low-level systems programming.

The problem itself is simple: given an integer n, determine whether it is a power of two. Numbers like 1, 2, 4, 8, 16, 32, and 64 should return true. Everything else returns false. You could solve this with a loop or logarithm, but the real lesson is the bit trick that makes the solution O(1).

If you only learn one bit manipulation technique for coding interviews, make it this one. The power of two leetcode problem is the cleanest introduction to a pattern that unlocks an entire category of problems.

The task is straightforward: given an integer n, return true if n is a power of two, and false otherwise. A power of two is any number that can be expressed as 2^k where k is a non-negative integer. The sequence starts at 1 (2^0), then 2, 4, 8, 16, 32, 64, 128, and so on.

The constraint that trips people up is that n can be zero or negative. Zero is not a power of two, and neither is any negative number. Your solution needs to handle these edge cases explicitly before applying any clever math or bit tricks.

Here is the complete leetcode 231 solution: return n > 0 and (n & (n - 1)) == 0. That is the entire function. One line. O(1) time, O(1) space. No loops, no division, no logarithms.

Why does this work? A power of 2 in binary has exactly one bit set to 1. The number 8 is 1000, 16 is 10000, 32 is 100000. When you subtract 1 from a power of 2, every bit below the single set bit flips to 1, and the set bit itself flips to 0. So n-1 has the exact opposite bit pattern in the positions that matter.

When you AND n with n-1, every bit cancels out and you get zero. For any number that is NOT a power of 2, there are multiple set bits, so clearing the lowest one still leaves bits remaining — the result is not zero. This is the n AND n-1 trick, and it is the foundation of bit manipulation in interviews.

Let us trace through concrete examples to build intuition. Take n = 8, which is a power of 2. In binary, 8 is 1000. Subtracting 1 gives 7, which is 0111. Now AND them: 1000 & 0111 = 0000. The result is zero, confirming 8 is a power of two.

Now take n = 6, which is NOT a power of 2. In binary, 6 is 110. Subtracting 1 gives 5, which is 101. AND them: 110 & 101 = 100. The result is 4, which is not zero. The trick correctly identifies 6 as not a power of two because it has two set bits, and clearing the lowest one still leaves one behind.

One more: n = 16 (10000). n-1 = 15 (01111). AND = 00000. Zero. Power of two confirmed. The pattern is always the same: for powers of 2, the single set bit and all the bits below it perfectly cancel out.

There is another valid approach: count the number of 1-bits in n. If there is exactly one 1-bit, the number is a power of two. You can count bits by repeatedly checking the lowest bit with n & 1 and right-shifting, or by using a built-in popcount function if your language provides one.

This approach works correctly and is easy to understand. In Python you could write bin(n).count("1") == 1, and in Java you could use Integer.bitCount(n) == 1. The time complexity is O(log n) for the manual counting approach or O(1) if the language uses a hardware popcount instruction.

While bit counting is perfectly acceptable in an interview, the n & (n-1) approach is more elegant and demonstrates deeper understanding. Interviewers testing bit manipulation want to see that you know this trick. It also generalizes — you can use n & (n-1) repeatedly to count all set bits, which is exactly how you solve Number of 1 Bits (#191).

The most common mistake on this problem is forgetting to check n > 0. The expression n & (n-1) == 0 is true when n = 0 because 0 & (-1) = 0. But zero is not a power of two. Without the guard clause, your solution silently returns the wrong answer for this input, and most test suites include it.

Another edge case is n = 1. Since 1 = 2^0, it is a valid power of two. In binary, 1 is just 1, and 1 & 0 = 0, so the trick handles it correctly as long as you allow n > 0 (not n > 1).

Negative numbers also need attention. In languages with signed integers, negative numbers have the sign bit set. Integer.MIN_VALUE in Java, for example, has exactly one 1-bit in two's complement representation (the sign bit), so n & (n-1) would return 0. But it is obviously not a power of two. The n > 0 check catches this case too.

The power of two leetcode problem is a gateway to an entire family of bit manipulation techniques. Once you understand that n & (n-1) clears the lowest set bit, you can solve Number of 1 Bits (#191) by counting how many times you can apply the trick before reaching zero. You can compute Hamming distance by XORing two numbers and counting the set bits in the result.

Bit manipulation problems appear less frequently than arrays or trees in interviews, but when they do appear, they are often the difference between a strong hire and a maybe. The candidates who know n & (n-1) solve these problems in seconds. The candidates who do not end up writing clunky loops that miss edge cases.

Practice this pattern alongside related problems: Number of 1 Bits (#191), Counting Bits (#338), Reverse Bits (#190), and Missing Number (#268). Once the bit tricks click, they stay with you — and YeetCode flashcards are designed to keep them fresh through spaced repetition so you never blank on interview day.