Power of Two

How it works

The largest power of two that fits in a 32-bit signed integer is 2^30 (since 2^31 exceeds the positive range). Any smaller power of two must divide evenly into 2^30.

If n is a power of two, then 2^30 mod n equals 0. If n is not a power of two, the division will have a remainder.

Steps

1. Check that n is positive.
2. Compute (1 << 30) % n (i.e., 2^30 mod n).
3. Return true if the result is 0.

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Things to watch for

Forgetting to Handle Non-Positive Numbers

A common mistake is forgetting that n must be strictly positive. Zero and negative numbers cannot be powers of two, but the bit manipulation tricks like n & (n - 1) == 0 will incorrectly return true for n = 0. Always check n > 0 before applying bit operations.

Integer Overflow in Iterative Approaches

When iteratively multiplying by 2 (e.g., x *= 2), the variable can overflow if using a 32-bit integer type. In languages like Java or C++, use a long or long long type for the accumulator to avoid wrapping around to negative values before reaching large inputs like 2^30.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and ((1 << 30) % n) == 0

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && ((1 << 30) % n) == 0;
    }
};