Pattern visualizer

Power of Two

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. Animated on: n = 16 (binary 10000) — determine whether n is a power of two..

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

time O(1)space O(1)step 1 / 10

[0]

[1]

[2]

[3]

[4]

line 2

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

Where to practice Bit Manipulation

Practice Bit Manipulation problems All Bit Manipulation problems Back to roadmap