Power of Two

Power of Two

What is this problem about?

The Power of Two problem asks whether a given integer is a power of 2. This easy coding problem has one of the most elegant O(1) bit manipulation solutions in all of programming — n > 0 && (n & (n-1)) == 0. The math, recursion, and bit manipulation interview pattern is demonstrated.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it's the gateway bit manipulation problem. The n & (n-1) trick — which clears the lowest set bit — is a fundamental operation that appears across dozens of bit manipulation problems.

Algorithmic pattern used

Bit manipulation. n & (n-1) removes the lowest set bit of n. A power of 2 has exactly one set bit, so after removing it, the result is 0. Combined with n > 0: return n > 0 && (n & (n-1)) == 0.

Alternative: n > 0 && (n & -n) == n (the only set bit equals n itself).

Example explanation

n=8 (binary: 1000). n-1=7 (0111). 1000 & 0111 = 0000 = 0. n>0 ✓. Return true. n=6 (binary: 0110). n-1=5 (0101). 0110 & 0101 = 0100 ≠ 0. Return false. n=1 (binary: 1). n-1=0 (0). 1 & 0 = 0. n>0 ✓. Return true (2^0=1).

Common mistakes candidates make

• Not handling n=0 (n & (n-1) = 0 for n=0, but 0 is NOT a power of 2).
• Not handling negative numbers (no negative power of 2 in integers).
• Using n % 2 check in a loop (O(log n), correct but not O(1)).
• Forgetting n=1 is valid (2^0).

Interview preparation tip

n & (n-1) is the most fundamental bit manipulation trick. It clears the lowest set bit. Memorize its three key applications: (1) check power of 2 ((n & (n-1)) == 0), (2) count set bits (Brian Kernighan's algorithm), (3) "is exactly one bit set." Practice this trick in multiple contexts — it's the foundation for Hamming weight, subsets, and graph problems.