Counting Bits

Bit manipulation · Reuse the answer after removing one bit · Easy · about 20 min

Why it matters

It is a gentle bridge between bit operations and dynamic programming.

How it connects

XOR gave you one identity. Now bit operations reveal a recurrence for every smaller number.

Try first

What number remains after n & (n - 1) removes n’s lowest set bit?

Interview cue

Removing the lowest set bit links each number to a smaller already-solved value.