Power of Two

Clear the lowest set bit with n & (n-1)

time O(1)space O(1)

A power of two has exactly one set bit. Subtracting 1 flips every bit below that lone set bit (and clears the bit itself), so ANDing n with n-1 wipes it out completely — the result is 0 only when there was exactly one bit to begin with.

Details

Animated on: n = 16 (binary 10000) — determine whether n is a power of two.

Problem:Power of TwoEasy

Clear the lowest set bit with n & (n-1)

step 1 / 10

[0]

[1]

[2]

[3]

[4]

n = 16. Check n > 0, then compare n to n-1 bit by bit using AND.

Pseudocode

1FUNCTION isPowerOfTwo(n):
2  IF n <= 0: RETURN false
3  m = n - 1
4  (m flips every bit below n's lowest set bit)
5  result = n AND m
6  (AND clears that one set bit entirely)
7  RETURN true if result is 0, otherwise false

← / → step · space play · Home restart

Every step in words

Show all 10 steps

n = 16. Check n > 0, then compare n to n-1 bit by bit using AND.
n = 16 in binary is 10000 (bit4 = 1, the only set bit).
n - 1 = 15 in binary is 01111 — subtracting 1 flips every bit below the lowest set bit.
bit4: n has 1, n-1 has 0 → AND = 0.
bit3: n has 0, n-1 has 1 → AND = 0.
bit2: n has 0, n-1 has 1 → AND = 0.
bit1: n has 0, n-1 has 1 → AND = 0.
bit0: n has 0, n-1 has 1 → AND = 0.
n & (n-1) = 10000 & 01111 = 00000 = 0.
The result is 0 and n > 0, so 16 is a power of two → true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Power of Two in the editor All Bit Manipulation problems Back to roadmap