Power of Four

main.md

Question

Approach

To check if n is a power of four, I first ensure that n is positive. Then, I use the property that a power of four is also a power of two, but with its single 1 bit in an odd position (0-indexed). The bitwise check (n & (n-1)) == 0 ensures it’s a power of two. To verify that the 1 bit is in an odd position, I use a mask: 0x55555555 (binary 01010101...), which only has 1s in odd bit positions. If n & 0x55555555 != 0, then n is a power of four.

Implementation

Complexities

• Time: O(1)
• Space: O(1)