Power of Four

Power of Four

What is this problem about?

The Power of Four problem asks whether a given integer is a power of 4 (4^0=1, 4^1=4, 4^2=16, ...). This easy coding problem has elegant O(1) solutions using bit manipulation and mathematical properties. The math, recursion, and bit manipulation interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it has multiple elegant solutions demonstrating bit manipulation mastery. It builds directly on Power of Two (n & (n-1) == 0) with an additional constraint on the bit position.

Algorithmic pattern used

Bit manipulation check. A power of 4 must be: (1) a power of 2 (n > 0 && (n & (n-1)) == 0), AND (2) the single set bit is at an even position (bit 0, 2, 4, ...). Check with mask 0x55555555 (alternating bits): n & 0x55555555 == n.

Combined: n > 0 && (n & (n-1)) == 0 && (n & 0x55555555) != 0.

Alternative: n > 0 && (n & (n-1)) == 0 && (n-1) % 3 == 0.

Example explanation

n=16 (binary: 10000). Power of 2? 16 & 15 = 0 ✓. Bit at position 4 (even) ✓. 16 & 0x55555555 = 16 ≠ 0 ✓. Return true.

n=8 (binary: 1000). Power of 2? ✓. Bit at position 3 (odd). 8 & 0x55555555 = 0 → not power of 4. Return false.

n=1: 4^0=1. Return true.

Common mistakes candidates make

• Checking only (n & (n-1)) == 0 (catches all powers of 2, not just 4).
• Not handling n=0 or n<0 edge cases.
• Using log4(n) with floating-point issues.
• Forgetting that n=1 (4^0) is a valid power of 4.

Interview preparation tip

Powers of 4 build on powers of 2 with an extra bit-position constraint. The mask 0x55555555 is the set of all even-position bits in 32-bit integers. Know the math trick too: (n-1) % 3 == 0 because 4^k - 1 = (4-1)(4^(k-1) + ... + 1) is always divisible by 3. Practice Power of Two, Power of Three, and Power of Four together to build a comprehensive toolkit for power-checking problems.