Skip to content

176 — Counting Bits

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

176 — Counting Bits

LeetCode 338 · Easy. Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1 bits in the binary representation of i.

🍽️ Intuition

This is the previous chapter's Number-of-1-Bits question, asked n + 1 times in a row — once for every integer from 0 up to n. The most direct way to answer it is to just do that literally: run an independent bit count for each i, one at a time, and drop each answer into the results array at position i. But repeating that work for every single i throws away a huge amount of structure: the bit count of i is tightly related to the bit count of a smaller number you've already computed. Specifically, chopping off i's last bit (i >> 1) gives you a number whose set-bit count you already know — you just need to add back 1 if the bit you chopped off was itself a 1 (i & 1). That turns "count 32 bits from scratch" into "look up one answer you already have, then add 0 or 1."

i = 13 = 0b1101

i >> 1 = 0b110 = 6         (chop off the last bit)
i & 1  = 1                  (the bit that got chopped off was a 1)

dp[13] = dp[6] + 1

dp[6] = 0b110 -> dp[3] + 0 = 2
dp[3] = 0b11  -> dp[1] + 1 = 2
dp[1] = 0b1   -> dp[0] + 1 = 1
dp[0] = 0

so dp[13] = dp[6] + 1 = 2 + 1 = 3   (0b1101 has three 1-bits)

🚩 Pattern-Recognition Cue

"Count set bits for every integer from 0 to n" signals a bottom-up bit-DP: whenever a per-number computation (here, a bit count) can be expressed in terms of a strictly smaller number's already-computed answer, filling an array in increasing order lets every entry reuse work instead of redoing it — dp[i] = dp[i >> 1] + (i & 1) is that relationship for bit counting specifically.

🐢 Brute Force

For every i from 0 to n, independently count its set bits by repeatedly checking the lowest bit and shifting right.

func countBitsBruteForce(_ n: Int) -> [Int] {
    var result = [Int](repeating: 0, count: n + 1)

    for i in 0...n {
        var num = i
        var count = 0
        while num != 0 {
            count += num & 1
            num >>= 1
        }
        result[i] = count
    }

    return result
}

// smoke test
print(countBitsBruteForce(2))   // [0, 1, 1]
print(countBitsBruteForce(5))   // [0, 1, 1, 2, 1, 2]
print(countBitsBruteForce(0))   // [0]

Big-O: O(n log n) time — each of the n + 1 numbers costs O(log i) to count its own bits independently. O(n) space for the output array (required by the problem itself).

🚀 Optimal

Fill the results array bottom-up: each dp[i] reuses the already-computed answer for i >> 1, adding 1 back if i's own last bit was set.

func countBits(_ n: Int) -> [Int] {
    var dp = [Int](repeating: 0, count: n + 1)
    guard n > 0 else { return dp }

    for i in 1...n {
        dp[i] = dp[i >> 1] + (i & 1)
    }

    return dp
}

// smoke test — same cases as the brute force
print(countBits(2))   // [0, 1, 1]
print(countBits(5))   // [0, 1, 1, 2, 1, 2]
print(countBits(0))   // [0]

Big-O: O(n) time — each of the n + 1 entries is filled with one array lookup and one bit check, O(1) amortized per entry. O(n) space for the output array, with no extra scratch space beyond it.

🔑 The Key Insight

The brute force's inner while loop recomputes a bit count from scratch for every single i, even though i's bit count and i >> 1's bit count differ by at most 1. Once you notice that i >> 1 is always a smaller number that's already been filled into the array earlier in the same pass, the whole problem collapses into a one-line recurrence: reuse what you already know, and account for the one bit that changed. The array isn't just the required output here — it doubles as the memo table the recurrence reads from.

🔗 Related Chapters

  • Arrays and Strings — the results array the optimal DP fills position by position, each entry built directly from an earlier one in the same array.
  • Bit Manipulation Tricks — the i >> 1 / i & 1 bit relationship between a number and its "last bit chopped off" version that the DP recurrence exploits.

🧸 Memory Sentence

Counting Bits is chopping off the last bit and looking up the answer for what's left — dp[i] = dp[i >> 1] + (i & 1) turns 32-bit counting into a one-line reuse.

✅ Check Your Understanding

  1. Why is i >> 1 guaranteed to already have its answer filled in by the time the loop reaches dp[i], for every i from 1 to n?
  2. Walk through why dp[13] = dp[6] + 1 but dp[12] = dp[6] + 0 — what's the one bit of information that changes between them?
  3. Why does the optimal function need the guard n > 0 check before the 1...n loop, when the brute force's 0...n loop needs no equivalent guard?
  4. The brute force's while num != 0 loop costs O(log i) per number. Why does that make the brute force's total cost O(n log n) rather than O(n), and where exactly does the optimal solution avoid that extra log i factor?

⬅️ Previous: Number of 1 Bits · Next: Reverse Bits ➡️

Clone this wiki locally