Count set bits for every number up to n

Question

For every integer i from 0 to n, compute the number of 1-bits in its binary representation. Return the full table. Counting each number's bits independently is O(n \log n), aim for O(n) total.

Accepted Answer

The identity i & (i - 1) clears the lowest set bit of i (subtracting 1 flips the trailing 100...0 to 011...1; AND-ing keeps everything above it). So i has exactly one more set bit than i & (i - 1), and that value is strictly smaller than i, hence already computed. A one-line DP falls out: Tracing n = 5: bits[3] = bits[2] + 1 = 2 (since 3 & 2 = 2), bits[4] = bits[0] + 1 = 1, bits[5] = bits[4] + 1 = 2. Table: [0, 1, 1, 2, 1, 2]. Time O(n), one table lookup per entry, space O(n) for the output. Two related tools to name: an equivalent DP bits[i] = bits[i 1] + (i & 1) (strip the last bit instead)…

Count set bits for every number up to n

Your answer

More Coding questions