We need to check if an integer n is a power of four.
👉 The trick is to combine power-of-two check with bit-position check:
n > 0→ only positive numbers can be powers of four.!(n & (n - 1))→ ensuresnis a power of two (only one bit is set).n & 0x55555555→ ensures that the single set bit is at an odd position (1, 3, 5…) which corresponds to powers of four in binary.
n & (n - 1) == 0→ classic power-of-two check.0x55555555→ binary:01010101010101010101010101010101, masks bits at positions for powers of four.- Combine all conditions with
&&→ concise one-liner.
- Powers of four in binary:
1, 100, 10000, 1000000… - Only one bit is set, and it’s always in an odd index (counting from 0).
- By checking both, we filter out powers of two that are not powers of four.
- Time: O(1) → all operations are constant time bitwise ops.
- Space: O(1) → only uses a few integer variables.