LeetCode 231 · Bits · Math

Power of Two, explained with a picture

A panel with exactly one switch on.

Bits · Math
▶ Watch it step by step

The problem

Decide whether n is a power of two.

Input:  16
Output: true

Picture it

Picture a switch panel: a power of two has exactly one switch on. n & (n − 1) turns off the lowest switch; if nothing is left, there was only one.

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

The key idea

n > 0 and n & (n − 1) == 0. O(1).

Python solution

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 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.