Topics › Bit Manipulation › Interview Problems

Counting Bits

Easy TUF ID 2393 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given a non-negative integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.

Constraints: 0 ≤ n ≤ 10^5. The follow-up asks for a linear-time, single-pass solution that does not call a built-in popcount such as Integer.bitCount.

Example 1

n = 2
answer = [0, 1, 1]              // 0 -> 0, 1 -> 1, 2 -> 10

Example 2

n = 5
answer = [0, 1, 1, 2, 1, 2]     // 3 = 11 has two ones, 4 = 100 has one, 5 = 101 has two

Approach 1: Brute force, count every number separately

Intuition. We already know how to count the set bits of one number: Brian Kernighan’s loop x &= x - 1 deletes the lowest 1 each round, so the number of rounds is the count. Run it independently for every i from 0 to n.

Algorithm.

1. Allocate ans of size n + 1.
2. For each i from 0 to n: copy i into x, run x &= x - 1 until x is 0, and store the number of rounds in ans[i].
3. Return ans.

static int[] bruteForce(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int x = i, count = 0;
        while (x != 0) {
            x &= x - 1;     // drop the lowest 1
            count++;
        }
        ans[i] = count;
    }
    return ans;
}

Complexity. Time O(n log n): number i has at most log2(i) + 1 bits, about 17 for 10^5, and the loop runs once per set bit. Space O(1) besides the output array.

That is fast enough in practice, but it throws away information. When we reach i = 13, we have already counted 6, 12 and every other smaller number, and 13 is closely related to several of them. The follow-up asks us to use that.

Approach 2: Optimal, DP on the last bit

Intuition. Look at i in binary and chop off its last bit. What remains is i >> 1 (that is, i / 2), and the bit we chopped off is i & 1:

13 = 1101  ->  13 >> 1 = 110 (6),  13 & 1 = 1

So bits(i) = bits(i >> 1) + (i & 1). Because i >> 1 < i for every i ≥ 1, filling the array in increasing order guarantees the value on the right is already computed when we need it. This is dynamic programming in its simplest form: the state is ans[i], the transition reads one smaller state, and the base case is ans[0] = 0, which Java’s zero-initialised array already provides.

Algorithm.

1. Allocate ans of size n + 1; ans[0] is 0.
2. For i from 1 to n: ans[i] = ans[i >> 1] + (i & 1).
3. Return ans.

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

Dry run for n = 8:

Complexity. Time O(n): constant work per index. Space O(1) beyond the output, which the problem requires anyway.

Approach 3: Optimal, DP on the lowest set bit

Intuition. Kernighan’s trick gives a second recurrence. i & (i - 1) is i with its lowest 1 cleared, so it has exactly one set bit fewer, and it is strictly smaller than i because a 1 was removed:

12 = 1100  ->  12 & 11 = 1000 (8),   so bits(12) = bits(8) + 1

Hence bits(i) = bits(i & (i - 1)) + 1, and again the smaller index is already filled in. This is exactly Approach 1’s loop with memoisation: the brute force walks 12 -> 8 -> 0 every time, while the DP stops after the first step and reuses the stored answer for 8.

Algorithm.

1. Allocate ans of size n + 1; ans[0] is 0.
2. For i from 1 to n: ans[i] = ans[i & (i - 1)] + 1.
3. Return ans.

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

Complexity. Time O(n), Space O(1) beyond the output.

A third recurrence works the same way using the highest bit: if p is the largest power of two not exceeding i, then bits(i) = 1 + bits(i - p), and p doubles every time i reaches the next power of two. All three are equally fast. Pick the one whose reason you can say out loud; the shift version is the easiest to explain.

Edge cases and pitfalls

• n = 0. The answer is [0], an array of length one. The loops start at 1, so they do nothing and the default 0 stays.
• Array length. The answer has n + 1 entries because both 0 and n are included. Allocating n is the classic off-by-one.
• Start the DP at 1, not 0. For i = 0 the “smaller” index 0 >> 1 or 0 & -1 is 0 itself, so ans[0] would read itself. It is the base case and must not be recomputed.
• i >> 1 versus i / 2. They agree for non-negative i, which is all we have here. The shift states the intent: drop the last bit.
• Overflow is impossible: counts stay below 32 and indices stay within n.

Related problems

• Number of 1 Bits counts the bits of one number and explains Kernighan’s trick in detail.
• Count the Number of Set Bits also asks for the total number of set bits over 1..n, which can be done without building this array.
• Check if a Number is Power of 2 or Not is the case where i & (i - 1) is 0.
• Introduction to Bits and Tricks collects the shift and mask identities used in all three recurrences.