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.

Two facts narrow the problem immediately. Negative numbers and zero can never be powers of two, since 2^x is positive for every integer x. And the constraint range goes up to 2^31 - 1, which leaves only 31 powers of two (2^0 through 2^30) inside the valid range.

What distinguishes powers of two from other numbers is 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 at least two bits set. The bit manipulation approaches below build directly on this property.

Key Constraints:

Intuition

If n is a power of two, dividing it by 2 repeatedly reaches 1, and every division along the way is exact. If n ever becomes odd before reaching 1, it has an odd factor other than itself, so it cannot be a power of two.

This is repeated removal of factors of 2. The number 16 goes 16, 8, 4, 2, 1, and every step divides exactly. The number 12 goes 12, 6, 3, and stops at an odd number that is not 1.

Algorithm

Example Walkthrough

Code

This runs in O(log n), but the follow-up asks for a solution without loops. The next approach answers in a single operation using the binary representation.

Intuition

Subtracting 1 from any positive number turns off its lowest set bit and turns on every bit below it. A power of two has exactly one set bit, so n - 1 flips that single bit to 0 and sets all lower bits to 1, leaving no bit in common with n. For example, 8 is 1000 and 7 is 0111, so 8 & 7 = 0.

For a number with more than one set bit, the subtraction only affects the lowest set bit and below; the higher set bits stay in place, so n & (n - 1) keeps at least one bit and is non-zero. The expression n & (n - 1) therefore equals 0 exactly when n has a single set bit. The positivity check is still needed, since 0 & (0 - 1) = 0 but zero is not a power of two. This operation that clears the lowest set bit is the same step used in Brian Kernighan's bit-counting algorithm.

Algorithm

Example Walkthrough

Code

This is O(1) and satisfies the follow-up. The next approach reaches the same answer with a different bit trick, n & (-n), which isolates the lowest set bit instead of clearing it. The same operation appears in Fenwick Trees.

Intuition

In two's complement, -n is computed by flipping all bits of n and adding 1. The expression n & (-n) keeps only the lowest set bit of n and clears the rest. When n has a single set bit, that lowest set bit is the whole number, so n & (-n) equals n. When n has more than one set bit, n & (-n) keeps just the lowest one and is therefore smaller than n. So n & (-n) == n holds exactly when n is a power of two, given n is positive.

Algorithm

Example Walkthrough

Code