Counting Bits
For every number from 0 to n, count how many set bits it has.
Pattern fit
This is a friendly bridge between DP and bit tricks because each answer can reuse a smaller number's answer after removing one low bit.
Key observation
bits[i] = bits[i & (i - 1)] + 1 is the cleanest recurrence.
Target complexity
O(n) / O(n)
How to break down the solution cleanly
This is a friendly bridge between DP and bit tricks because each answer can reuse a smaller number's answer after removing one low bit.
bits[i] = bits[i & (i - 1)] + 1 is the cleanest recurrence.
Define what each bit means.
Pick the one operation that naturally updates that meaning.
Reference implementation
Python# Generic pattern template
x & (x - 1) # clear lowest set bit
x & -x # isolate lowest set bit
x | (1 << i) # set bit i
x & ~(1 << i) # clear bit i
x ^ (1 << i) # toggle bit i
(x >> i) & 1 # read bit i
Common pitfalls
Treating each number independently and missing the recurrence.
Not understanding why i & (i - 1) removes the lowest set bit.
Common follow-ups
What alternative recurrence uses right shift?
Why is this both DP and bit manipulation?
Continue with related problems
Build repeatable depth inside the Bit Manipulation cluster before moving on.