We need to determine whether a given integer is a power of two. Powers of two form the sequence 1, 2, 4, 8, 16, 32, 64, and so on. Each one is exactly double the previous.

A couple of things to notice right away. First, negative numbers and zero can never be powers of two since 2^x is always positive for any integer x. Second, the constraint range goes up to 2^31 - 1, which means there are only 31 possible powers of two (2^0 through 2^30) within the valid range. That's a tiny set, and this observation opens the door to several clever approaches.

The real question is: what property distinguishes powers of two from other numbers? The answer lies in their binary representation. A power of two has exactly one bit set to 1. For example, 8 is 1000 in binary, 16 is 10000, and 32 is 100000. Every other positive integer has more than one bit set. This is the key insight that unlocks the bit manipulation approaches.

Key Constraints:

Intuition

The most straightforward idea: if n is a power of two, we should be able to keep dividing it by 2 until we reach 1. At every step, the number must be evenly divisible by 2. If at any point it's odd (and not equal to 1), it can't be a power of two.

Think of it like peeling off factors of 2. The number 16 goes 16 -> 8 -> 4 -> 2 -> 1. Every step divides cleanly. But 12 goes 12 -> 6 -> 3, and now we're stuck with an odd number that isn't 1.

Algorithm

Example Walkthrough

Code

The iterative approach works, but the follow-up asks for a solution without loops. Can we determine the answer in a single operation by looking at the binary representation?

Intuition

A power of two has exactly one bit set in binary. When you subtract 1 from a power of two, that bit flips to 0 and all the lower bits flip to 1. For example, 8 is 1000 and 7 is 0111. So n and n - 1 have no bits in common, meaning n & (n - 1) equals 0.

For non-powers of two, subtracting 1 only flips the lowest set bit and the bits below it. The higher set bits remain, so n & (n - 1) gives a non-zero result. We just need to also check that n is positive, since 0 & (-1) = 0 and zero is not a power of two.

Algorithm

Example Walkthrough

Code

Approach 2 is already O(1) and satisfies the follow-up. But there's another bit manipulation technique using n & (-n) that offers a different perspective and connects to Fenwick Trees.

Intuition

In two's complement, -n is computed by flipping all bits and adding 1. The expression n & (-n) isolates the lowest set bit of n. For a power of two, there's only one set bit, so n & (-n) returns n itself. For any other number, n & (-n) returns something smaller than n.

Algorithm

Example Walkthrough

Code