Power of Four
Determine whether an integer is a power of four using bit position, not just the power-of-two test.
- -2³¹ <= n <= 2³¹ - 1
Intuition
Power of four leetcode problem 342 tests whether an integer is a power of four, ideally without loops or recursion.
Every power of four is also a power of two, so the check has two parts. The first is the standard bit trick:
- n > 0 && (n & (n − 1)) == 0 confirms exactly one bit is set, which is what makes a number a power of two.
The positive test is not optional — for n = 0 the expression is also true, and zero is not a power of anything.
Distinguishing powers of four from other powers of two is the interesting half. Writing them in binary shows the pattern: 1, 100, 10000, 1000000 — the single set bit always sits at an even index, counting from zero on the right. Powers of two that are not powers of four have their bit at an odd index.
Two ways to test that:
A mask of 0x55555555 has 1s at every even position, so (n & 0x55555555) != 0 confirms the set bit lands there. That is one AND, no loop.
Alternatively, (n − 1) % 3 == 0. This works because 4 ≡ 1 (mod 3), so every power of four is 1 more than a multiple of 3. It is neat but obscures the reasoning.
The logarithm approach — checking whether log(n) / log(4) is an integer — is unreliable. Floating-point rounding makes it report false for some large valid inputs, which is why bit manipulation is preferred here.
All variants are O(1) in time and space.
A power of four is a power of two with its single bit at an even position. The bit test handles the first half; (n - 1) % 3 == 0 handles the second, because 4^k − 1 is always divisible by 3 while 2^odd − 1 is not.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(1) time and O(1) space.
Confirm a single set bit
n > 0 && (n & (n - 1)) == 0 means exactly one bit is set — the definition of a power of two. The positive test excludes zero, which passes otherwise.
Find the distinguishing pattern
Written in binary, powers of four are 1, 100, 10000 — the set bit always sits at an even index. Powers of two that are not powers of four sit at odd indices.
Test with a mask
0x55555555 has 1s at every even position, so (n & 0x55555555) != 0 confirms the bit lands there. One AND, no loop.
Or use the modulo trick
(n - 1) % 3 == 0 works because 4 ≡ 1 (mod 3), so every power of four is one more than a multiple of 3. Neat, but it hides the reasoning.
Avoid the logarithm
Checking log(n) / log(4) for an integer is unreliable — floating-point rounding reports false for some large valid inputs.
Cost of the check
Two constant-time bit operations give O(1) time and O(1) space, with no iteration at all.
Solution & live demo
Common pitfalls
Only checking for a single set bit
return n > 0 and (n & (n - 1)) == 0
return single_bit and (n - 1) % 3 == 0
That accepts 8, 32, and every other odd power of two. The position of the bit matters, not just that there's exactly one.
Testing divisibility by 3 without the bit check
return n > 0 and (n - 1) % 3 == 0
single_bit = n > 0 and (n & (n - 1)) == 0
Many non-powers satisfy it — 7, 10, 13 all give (n-1) % 3 == 0. Both conditions are necessary; neither alone is sufficient.
Using a floating-point logarithm
return math.log(n, 4).is_integer()
return single_bit and (n - 1) % 3 == 0
Rounding makes log(64, 4) evaluate to 2.9999999999999996 on some inputs, rejecting genuine powers of four. Integer bit and modulo operations are exact.
Edge cases
passes single-bit test but (8-1)%3=1 != 0, correctly returns False
passes both checks, returns True
fails the n > 0 guard before any bit test runs
single bit at position 0 (even), (1-1)%3=0, returns True