Counting Bits

Counting Bits takes a single-number trick and stretches it across many numbers. You could count the ones for each number on its own. But there is a smarter path. You reuse answers you already found. That reuse is dynamic programming, and this problem is a clean way to learn it.

🎯 The Problem

You get a number n. You build a list of bit counts for every number from 0 to n. The count of 1 bits in a number is called its bit count.

The rules:

• The list has n + 1 slots, one for each number from 0 to n.
• Position i holds the number of 1 bits in the number i.
• Return the finished list.

Let us say n is 5. We look at every number from 0 to 5. The result is the list of their bit counts.

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

Explanation:
0 -> 000 -> 0 ones
1 -> 001 -> 1 one
2 -> 010 -> 1 one
3 -> 011 -> 2 ones
4 -> 100 -> 1 one
5 -> 101 -> 2 ones

So we want one answer per number, packed into a list.

Here is the binary of each number from 0 to 5. The bit counts on the right are what we collect.

🐢 Approach 1: Count Each Number From Scratch (Brute Force)

The idea in one line: count the 1 bits of every number on its own.

The idea:

• Loop every number from 0 to n.
• For each one, run a small inner loop that counts its 1 bits.
• Use the n & (n - 1) trick, which clears the lowest 1 bit each pass.

How it works:

• Each clear removes one 1 bit and adds one to that number’s count.
• Store the count at position i.

Why it is weak:

• Every number starts counting from zero again.
• The inner loop runs once per 1 bit, for every number.
• Total work grows with n times the bit width.

Here is the count-from-scratch code:

def count_bits(n):
    answer = []
    for value in range(n + 1):
        count = 0
        x = value
        while x:
            count += x & 1
            x >>= 1
        answer.append(count)
    return answer

⚡ Approach 2: Dynamic Programming Reuse (Best)

The idea in one line: solve each number once, then reuse that answer for bigger numbers.

The idea:

• This is dynamic programming, where we reuse finished answers instead of recomputing them.
• We go in order from small to large, so smaller answers are always ready.

How it works:

• i & (i - 1) clears the lowest 1 bit of i, giving a smaller number.
• That smaller number is already counted.
• i has exactly one extra 1 bit, the one we cleared.
• So result[i] = result[i & (i - 1)] + 1.

Why it is fast:

• Each number costs one single step.
• No inner loop at all.
• The whole list is built in one clean pass.

Here is a picture of the recurrence for a few numbers. Each one points to the smaller number it reuses.

Steps to Solve

1. Make a list of size n + 1 filled with zeros.
2. Set position 0 to 0, since zero has no 1 bits.
3. Loop i from 1 up to n.
4. Set result[i] to result[i & (i - 1)] + 1.
5. Each step reuses an already-counted smaller number.
6. Return the finished list.

#include <stdio.h>

int main(void) {
    int n = 5;
    int result[6];               // size n + 1
    result[0] = 0;               // zero has no 1 bits
    for (int i = 1; i <= n; i++) {
        result[i] = result[i & (i - 1)] + 1;  // reuse smaller answer
    }

    printf("[");
    for (int i = 0; i <= n; i++) {
        printf("%d", result[i]);
        if (i < n) printf(", ");
    }
    printf("]\n");
    return 0;
}

[0, 1, 1, 2, 1, 2]

#include <iostream>
#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> result(n + 1, 0);  // start all at zero
    for (int i = 1; i <= n; i++) {
        result[i] = result[i & (i - 1)] + 1;  // reuse smaller answer
    }
    return result;
}

int main() {
    vector<int> result = countBits(5);
    cout << "[";
    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i + 1 < (int)result.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[0, 1, 1, 2, 1, 2]

import java.util.Arrays;

public class CountingBits {
    public static int[] countBits(int n) {
        int[] result = new int[n + 1];   // all start at 0
        for (int i = 1; i <= n; i++) {
            result[i] = result[i & (i - 1)] + 1;  // reuse smaller answer
        }
        return result;
    }

    public static void main(String[] args) {
        int[] result = countBits(5);
        System.out.println(Arrays.toString(result));
    }
}

[0, 1, 1, 2, 1, 2]

def count_bits(n):
    result = [0] * (n + 1)          # all start at zero
    for i in range(1, n + 1):
        result[i] = result[i & (i - 1)] + 1  # reuse smaller answer
    return result


print(count_bits(5))

[0, 1, 1, 2, 1, 2]

function countBits(n) {
  const result = new Array(n + 1).fill(0); // all start at zero
  for (let i = 1; i <= n; i++) {
    result[i] = result[i & (i - 1)] + 1; // reuse smaller answer
  }
  return result;
}

console.log(countBits(5));

[ 0, 1, 1, 2, 1, 2 ]

Let us go through the Python version line by line and see why the formula holds.

def count_bits(n):
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i & (i - 1)] + 1
    return result

The line result = [0] * (n + 1) makes a list with one slot for every number from 0 to n. We fill it with zeros. Position 0 is already correct, because the number zero has no 1 bits.

The line for i in range(1, n + 1): walks from 1 up to n. We start at 1 because 0 is already done. We go in order so that smaller answers are always ready before we need them.

The line result[i] = result[i & (i - 1)] + 1 is the whole solution. The piece i & (i - 1) clears the lowest 1 bit of i, giving a smaller number we have already counted. We add 1 because i has exactly one more 1 bit than that smaller number. So we reuse old work and add one.

The line return result hands back the full list of bit counts.

⏱️ Time and Space Complexity

The count-each-number way runs a small loop for every number, so its time is about O(n times bit width). The dynamic programming way does just one step per number, because it reuses a smaller answer. So it is a clean O(n). Both store the output list, so memory is O(n). The reuse is what removes the inner loop and brings the time down.

🧩 Key Takeaways

• ✅ The goal is a list of 1-bit counts for every number from 0 to n.
• ✅ The slow way counts each number on its own from scratch.
• ✅ The fast way reuses smaller answers, which is dynamic programming.
• ✅ The formula is result[i] = result[i & (i - 1)] + 1.
• ✅ Reuse turns the work into a clean O(n) pass.

🚀 What’s Next?

• Number of 1 Bits
• Reverse Bits