Power of Four
Determine whether an integer is a power of four using bit position, not just the power-of-two test.
Open on LeetCode ↗Intuition
The trap is reusing the power-of-two check and calling it done: 8 passes n & (n-1) == 0 because it has exactly one set bit, but 8 is 2^3, not a power of four. What power-of-two misses is WHERE that single bit sits. Powers of four (1, 4, 16, 64, ...) always have their lone set bit at an even position (0, 2, 4, ...), while powers of two that aren't powers of four (2, 8, 32, ...) have it at an odd position. So the fix is: keep the single-set-bit test as a first filter, then add a second check that the bit position is even -- either with a mask like 0x55555555 that only has bits set at even positions, or the arithmetic shortcut that (n-1) is divisible by 3 exactly when n is a power of four.
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
Filter to single-set-bit values
First confirm n > 0 and n & (n - 1) == 0, exactly as in Power of Two. This narrows candidates down to powers of two, but that set still includes non-powers-of-four like 2 and 8.
Check the bit sits at an even position
For a value that passed the single-bit test, check (n - 1) % 3 == 0. This works because powers of four minus one (0, 3, 15, 63, ...) are always multiples of 3, while powers of two at odd positions minus one (1, 7, 31, ...) are not.
Combine both conditions
Return True only when both the single-bit test and the even-position test pass. Either check alone is insufficient -- the single-bit test overaccepts values like 8, and the mod-3 test alone would need the single-bit guard to avoid false positives on numbers with multiple bits set.
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