Power of Four

Time Complexity: O(1)
Space Complexity: O(1)

Algorithms Math

Given an integer n, return true if it is a power of four.

Input: 16 → Output: true

Input: 5 → Output: false

Solution Approach

A power of four must be a power of two (only one bit set), and that bit must be in an odd position (bit 0, 2, 4, ...).

n > 0 AND n has only one bit set (power of 2) AND the bit is at an even position.
Mask 0x55555555 = 01010101...01 selects bits at even positions.
Return n > 0 && (n & (n-1)) == 0 && (n & 0x55555555) != 0.

Java

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n-1)) == 0 && (n & 0x55555555) != 0;
    }
}