Counting bits

Count the 1 bits of every number from 0 to n in one pass, reusing the answer for half the number.

The idea

Shifting i right by one drops its lowest bit and keeps every other bit, so i has exactly the set bits of i >> 1, plus one more if the dropped bit (i & 1) was 1. i >> 1 is smaller than i, so its count is already in the table.

Code

public int[] CountBits(int n) {
    var dp = new int[n + 1]; // dp[0] = 0: zero has no set bits
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

Tips

• Another O(n) form: dp[i] = dp[i & (i - 1)] + 1, because i & (i - 1) clears the lowest set bit.
• Counting each number separately with Kernighan's trick is O(n log n); this reuses earlier answers to get O(n).

In the .NET library

For a single number, BitOperations.PopCount((uint)i) is one CPU instruction. The DP matters when the interviewer asks for all of 0..n without built-ins.