Free lesson · DSA Mastery - Interview Prep, End to End

Counting Bits

Medium7 min readdsabit-manipulation

Counting Bits

Counting Bits is the natural generalization of Number of 1 Bits. Instead of computing bit count for a single number, you compute it for every integer in [0, n]. The naive approach calls a bit-counter n + 1 times - O(n log n) total. The clever approach uses dynamic programming to reuse previous results, achieving O(n).

The DP recurrence is one of the cleanest in bit manipulation. The relation bits[i] = bits[i >> 1] + (i & 1) (or alternatively bits[i] = bits[i & (i - 1)] + 1) captures the structure perfectly.

The Problem

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's in the binary representation of i.

Example 1:

Input:  n = 2
Output: [0, 1, 1]

Explanation:
  0 -> 0 bits
  1 -> 1 bit
  2 -> 1 bit (binary 10)

Example 2:

Input:  n = 5
Output: [0, 1, 1, 2, 1, 2]

Explanation:
  0 -> 0
  1 -> 1
  2 -> 10 -> 1
  3 -> 11 -> 2
  4 -> 100 -> 1
  5 -> 101 -> 2

Constraints:

• 0 <= n <= 10^5

Follow-up: Can you implement a solution with O(n) time complexity and O(1) extra space (excluding the output)? Can you do it without using any built-in functions?

Approach

Two clean DP approaches.

Approach 1: bits[i] = bits[i >> 1] + (i & 1)

Right-shifting i by 1 removes the lowest bit. So i >> 1 has all the same bits as i except for the lowest one. The lowest bit of i is i & 1 (0 or 1).

So: bits[i] = bits[i >> 1] + (i & 1).

This works because i >> 1 < i, so bits[i >> 1] has already been computed when we process i.

Approach 2: bits[i] = bits[i & (i - 1)] + 1

Recall from Number of 1 Bits: i & (i - 1) clears the lowest set bit of i. So i & (i - 1) has exactly one fewer set bit than i.

So: bits[i] = bits[i & (i - 1)] + 1.

This works because i & (i - 1) < i, so the value has already been computed.

Both approaches are O(n) time and use the output array as the only working memory.

graph TD
    A["bits[0] = 0"] --> B["For i = 1 to n"]
    B --> C["bits[i] = bits[i >> 1] + (i & 1)"]
    C --> D{"More?"}
    D -->|Yes| B
    D -->|No| E["Return bits"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the DP recurrence. We initialize bits at zero equal to zero. For each i from one to n, we compute bits at i as bits at i shifted right by one plus i bitwise AND one. The right shift removes the lowest bit; the AND extracts it. The recurrence reuses previously computed values.

Code Implementation

public static int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
}

// Usage:
// System.out.println(Arrays.toString(countBits(2)));  // [0, 1, 1]
// System.out.println(Arrays.toString(countBits(5)));  // [0, 1, 1, 2, 1, 2]

This Java code implements Counting Bits using a one-line DP recurrence. We allocate an array of size n plus one. We initialize bits at zero implicitly to zero (Java default). For each i from one to n, we set bits at i to bits at i shifted right one, plus i bitwise AND with one. The result array holds the bit counts for zero through n.

The variant using Brian Kernighan's trick:

public static int[] countBitsBK(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}

Both versions are O(n) time and O(1) auxiliary space (the output is required). Pick whichever you find more memorable.

Walkthrough

Trace on n = 5 with the first DP recurrence.

Initial: bits = [0, 0, 0, 0, 0, 0] (length 6, indices 0..5).

i=1: bits[1] = bits[1 >> 1] + (1 & 1) = bits[0] + 1 = 0 + 1 = 1.
     bits = [0, 1, 0, 0, 0, 0].

i=2: bits[2] = bits[2 >> 1] + (2 & 1) = bits[1] + 0 = 1 + 0 = 1.
     bits = [0, 1, 1, 0, 0, 0].

i=3: bits[3] = bits[3 >> 1] + (3 & 1) = bits[1] + 1 = 1 + 1 = 2.
     bits = [0, 1, 1, 2, 0, 0].

i=4: bits[4] = bits[4 >> 1] + (4 & 1) = bits[2] + 0 = 1 + 0 = 1.
     bits = [0, 1, 1, 2, 1, 0].

i=5: bits[5] = bits[5 >> 1] + (5 & 1) = bits[2] + 1 = 1 + 1 = 2.
     bits = [0, 1, 1, 2, 1, 2].

Return [0, 1, 1, 2, 1, 2].

Result: [0, 1, 1, 2, 1, 2].

Each entry is computed in O(1) by reading one previous entry and adding 0 or 1. No nested loop, no bit-by-bit counting.

Complexity Analysis

Why It Is O(n) Time

Single loop from 1 to n. Each iteration does constant work (one read, one AND, one add, one write). Total: O(n).

Why It Is O(1) Auxiliary Space

The output array is required (the problem says "return an array of length n + 1"). Beyond the output, we use only loop counters. O(1) auxiliary.

Why DP Beats the Naive Approach

Naive: call hammingWeight(i) for each i. With Brian Kernighan, each call is O(log i). Total: O(n log n).

DP: each bits[i] is computed in O(1) from a previously stored value. Total: O(n).

For n = 10^5, naive is ~5 million ops, DP is ~10^5 ops. DP is 50x faster.

Why Both Recurrences Work

The two recurrences come from different "decompositions" of the bit count:

• bits[i] = bits[i >> 1] + (i & 1): separate the lowest bit from the rest.
• bits[i] = bits[i & (i - 1)] + 1: separate the lowest set bit from the rest.

Both are valid because both subproblems (i >> 1 and i & (i - 1)) are smaller than i, so they've been computed by the time we need them.

Variations & Follow-ups

What if n could be very large (10^18)?

The output array would be too big. The problem wouldn't make sense as stated. But the recurrence still lets you compute bits[k] for any single k in O(log k) time without storing intermediate values:

public static int countBitsSingle(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;
}

This is essentially Number of 1 Bits via the shift-and-check approach.

Why use i >> 1 instead of i / 2?

They're equivalent for non-negative integers. The shift is conventionally preferred in bit-manipulation contexts because it emphasizes the bit-level structure.

What if you wanted the bit count using Long.bitCount for each i?

public static int[] countBitsLibrary(int n) {
    int[] bits = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        bits[i] = Integer.bitCount(i);
    }
    return bits;
}

This is O(n) too (Java's bitCount is O(1)). Slightly slower than DP in practice because of the per-call overhead, but functionally equivalent.

What if the recurrence weren't allowed (no DP)?

Use SWAR or lookup tables. But for the standard problem, DP is the expected answer.

What about edge cases?

• n = 0: Returns [0] (just the zero bit count for 0). The loop doesn't execute.
• n = 1: Returns [0, 1]. One iteration of the loop.
• Powers of 2 (n = 2, 4, 8, ...): Bits jump from previous max to 1 (bits[2] = 1, bits[4] = 1, bits[8] = 1).
• n just below a power of 2 (n = 7, 15, 31, ...): bits[n] is the position of the highest bit + 1 (bits[7] = 3, bits[15] = 4).

Common Interview Pitfalls

• Calling Brian Kernighan in a loop. Works (O(n log n)) but misses the DP insight that makes O(n) possible.
• Trying to derive bits via mathematical formulas. Closed-form for "count bits up to n" exists but is far more complex than the DP. Use DP.
• Off-by-one in the array size. It's n + 1 (to include both 0 and n).
• Using i / 2 and getting confused with rounding. For non-negative integers, i / 2 and i >> 1 are identical. Use whichever.
• Initializing bits[0] explicitly. Java arrays initialize to 0 by default, so this is implicit. Don't write bits[0] = 0; redundantly (it's not wrong, just verbose).

Why This Problem Matters

Counting Bits demonstrates DP via bit-level recurrences. The technique generalizes:

• Subset sums - compute properties of all 2^n subsets via incremental updates.
• DP over bitmasks (Section 19, 30) - use the bit pattern itself as DP state.
• Sum-over-subsets DP - efficient computation of aggregate functions over subset lattices.

The two recurrences (i >> 1 and i & (i - 1)) also illustrate that multiple DP transitions can solve the same problem. Recognizing alternative recurrences is a useful skill - sometimes one is easier to derive, the other easier to extend.

The connection back to Brian Kernighan in bits[i] = bits[i & (i - 1)] + 1 is also worth appreciating. The bit-manipulation primitives from Number of 1 Bits show up again here as DP transitions.

The next topic, Hamming Distance, applies bit counting to a different question - measuring the number of differing bits between two numbers.

Back to DSA Mastery - Interview Prep, End to End