LeetCode 342 · Bits · Math

Power of Four, explained with a picture

One switch on, at an even position.

Bits · Math
▶ Watch it step by step

The problem

Decide whether n is a power of four.

Input:  64
Output: true

Picture it

Picture the switch panel again: exactly one switch on, and it must sit at an even position (1, 4, 16, 64…). A mask of every even position checks that.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Power of two and n & 0x55555555 ≠ 0. O(1).

Python solution

def is_power_of_four(n):
    return n > 0 and n & (n - 1) == 0 and n & 0x55555555 != 0

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.