Power of Four

easy bit manipulation math

Problem

Return true if n is a power of four. Solve it in O(1) — no loops or recursion.

Inputn = 16

Outputtrue

16 = 4² — its only set bit is at an even position.

def is_power_of_four(n):
    if n <= 0:
        return False
    if n & (n - 1):
        return False
    return (n & 0xAAAAAAAA) == 0

function isPowerOfFour(n) {
  if (n <= 0) return false;
  if ((n & (n - 1)) !== 0) return false;
  return (n & 0xAAAAAAAA) === 0;
}

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) return false;
        if ((n & (n - 1)) != 0) return false;
        return (n & 0xAAAAAAAA) == 0;
    }
}

bool isPowerOfFour(int n) {
    if (n <= 0) return false;
    if (n & (n - 1)) return false;
    return (n & 0xAAAAAAAA) == 0;
}

Explanation

A power of four is special in two ways: it is a power of two (so it has exactly one set bit), and that single bit sits at an even position (bit 0, 2, 4, ...). We check both facts with constant-time bit tricks — no loops needed.

First, n must be positive, so we reject n <= 0 right away.

Next we confirm it is a power of two. The test n & (n - 1) equals 0 only when n has a single set bit, so if that AND is non-zero we return false.

Finally we check the bit's position with the mask 0xAAAAAAAA, whose ones sit at every odd position. If n & 0xAAAAAAAA is 0, the lone bit is at an even position, which means it is a power of four.

Example: n = 16 = 10000. It has one bit, and that bit is at position 4 (even), so 16 & 0xAAAAAAAA = 0 and the answer is true. Compare 8 = 1000, whose bit is at odd position 3 — a power of two but not of four.

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