All patterns
Bit Manipulation
Greedy Algorithms & Mathematical Optimization
Intermediate
Interactive
Clear the lowest set bit with n & (n-1).
Time
O(number of set bits)
Space
O(1)
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.
The idea
Binary operations manipulate compact state directly. Brian Kernighan's algorithm counts one-bits by repeatedly clearing the lowest set bit, so it performs one iteration per set bit rather than per binary digit.
Analogy
This visualization makes the state transitions behind bit manipulation explicit, one decision at a time.
When to reach for it
- The problem exhibits this pattern's defining invariant.
- A direct brute-force approach repeats work or explores unnecessary choices.
- You need a standard interview-ready template.
Language-independent template
count = 0
while n:
n = n & (n - 1)
count += 1Complexity — time O(number of set bits), space O(1).
Common mistakes
- Choosing the wrong state or invariant.
- Updating state before preserving the value needed next.
- Missing a boundary or base case.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Easy
Number of 1 BitsLC 191
Return the Hamming weight of an unsigned integer.
Medium
Sum of Two IntegersLC 371
Add two integers without using plus or minus.
Hard
Find the minimum legal bit flips needed to reduce n to zero.
Variations
Change the input to exercise another path.
Adapt the invariant to a related optimization or counting problem.