#72 · Bit Manipulation

Counting Bits

Given n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i.

EasyLeetCode

Bit being examined
Counted / set / result
Related bit
Cleared / carried

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Table indexed by the number

ans[i] depends only on a smaller number: i >> 1 (drop the last bit) or i & (i − 1) (clear the lowest 1 bit). Filling the table in increasing order guarantees the smaller entry is ready.

Memory layout

A flat array of n + 1 small integers.

Operation	Cost
time	O(n)
space	O(n) for the output

Population count of a single number

Counting the bits of one number costs O(32) or O(bits set). Doing it independently for every i multiplies that cost by n.

Memory layout

One register.

Operation	Cost
per number	O(32) or O(set bits)

Why it fits

Consecutive integers share most of their bits, so counts can be derived rather than recomputed.
Two different recurrences work: remove the last bit (shift) or remove the lowest set bit (n & (n − 1)). Both reduce i to a strictly smaller index.
Because the answers are needed for every i anyway, a bottom-up table is the natural structure.

Why alternatives degrade

Counting each number separately:: It repeats work: the bits of 13 are just the bits of 6 plus one more.
Recursion without a table:: popcount(i) = popcount(i >> 1) + (i & 1) recomputes the chain for every i: O(n log n).
Lookup of a precomputed table for all 32 bits:: Too large; the point of the problem is that the table you need is the answer itself.

Four approaches, from naive to production

1 · beginner

Test 32 positions for every number

time O(32 · n)space O(n) for the output

For each i from 0 to n, loop over the 32 bit positions and count the ones.

vector<int> countBits(int n) {
    vector<int> ans;
    for (int i = 0; i <= n; i++) {
        int count = 0;
        for (int b = 0; b < 32; b++) {
            if ((i >> b) & 1) count++;
        }
        ans.push_back(count);
    }
    return ans;
}

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0;
        for (int b = 0; b < 32; b++) {
            if (((i >>> b) & 1) != 0) count++;
        }
        ans[i] = count;
    }
    return ans;
}

def count_bits(n):
    ans = []
    for i in range(n + 1):
        count = 0
        for b in range(32):
            if (i >> b) & 1: count += 1
        ans.append(count)
    return ans

function countBits(n: number): number[] {
  const ans: number[] = [];
  for (let i = 0; i <= n; i++) {
    let count = 0;
    for (let b = 0; b < 32; b++) {
      if ((i >>> b) & 1) count++;
    }
    ans.push(count);
  }
  return ans;
}

Flaws & bottlenecks

Does 32 tests for every number, even for small ones with few bits.
Ignores the relationship between neighbouring numbers.
Needs the unsigned right shift in languages with signed integers.

Interviewer cross-questions

What is wasted?

Say: Almost all of the 32 tests are on leading zeros, and the count of i is closely related to that of a smaller number, which was already computed.

How could you stop the inner loop earlier?

Say: Loop while the number is non-zero (shifting right), or clear one set bit at a time.

Is the complexity really linear?

Say: O(32 · n) is linear in n for a fixed word size, but with a large constant factor.

2 · intermediate

Kernighan's method for each number

time O(n · bits set)space O(n) for the output

For each i, repeatedly clear the lowest set bit with x &= x − 1 and count how many times that is possible.

vector<int> countBits(int n) {
    vector<int> ans;
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        ans.push_back(count);
    }
    return ans;
}

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        ans[i] = count;
    }
    return ans;
}

def count_bits(n):
    ans = []
    for i in range(n + 1):
        count, x = 0, i
        while x != 0:
            x &= x - 1
            count += 1
        ans.append(count)
    return ans

function countBits(n: number): number[] {
  const ans: number[] = [];
  for (let i = 0; i <= n; i++) {
    let count = 0, x = i;
    while (x !== 0) {
      x &= x - 1;
      count++;
    }
    ans.push(count);
  }
  return ans;
}

Flaws & bottlenecks

Still a loop per number: up to log n iterations each, O(n log n) in total.
Each number is counted independently, ignoring earlier results.
Uses a working copy x for every i.

Interviewer cross-questions

How many iterations does the inner loop take?

Say: Exactly the number of ones in i, so on average about half of log₂ n.

Can you avoid the inner loop entirely?

Say: Yes: ans[i] = ans[i & (i − 1)] + 1, because clearing the lowest set bit gives a smaller number whose answer is known.

Why does x &= x − 1 terminate?

Say: It strictly decreases x and removes a 1 each time, so after popcount(x) steps x is 0.

3 · advanced

DP with i >> 1

time O(n)space O(n)

ans[i] = ans[i >> 1] + (i & 1): shifting right drops the last bit, whose count is already in the table, and the dropped bit adds 0 or 1.

vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

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

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

function countBits(n: number): number[] {
  const ans = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
}

Flaws & bottlenecks

The relation has to be seen or proved; it is a small insight.
Uses the output array as working memory, so it cannot be done in place of a smaller structure.
For ans[0] the loop must start at 1 (ans[0] = 0 is the base case).

Interviewer cross-questions

Why is ans[i >> 1] already computed?

Say: i >> 1 is at most i / 2, which is smaller than i for i ≥ 1, and the loop goes in increasing order.

What does i & 1 add?

Say: The last bit of i, which was dropped by the shift: 1 if i is odd, 0 if even.

How does this compare to the lowest-set-bit version?

Say: Both are O(n) with one lookup. This one needs a shift and a mask; the other needs a subtract and an AND, and always adds exactly 1.

4 · expert

DP with i & (i − 1)

time O(n)space O(n)

ans[i] = ans[i & (i − 1)] + 1: clearing the lowest set bit gives a smaller number with exactly one fewer 1 bit.

vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i & (i - 1)] + 1;
    }
    return ans;
}

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

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

function countBits(n: number): number[] {
  const ans = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i & (i - 1)] + 1;
  }
  return ans;
}

Flaws & bottlenecks

Relies on the less common identity i & (i − 1).
ans[0] = 0 must be set before the loop (the array initialisation does it).
The reuse pattern does not extend easily to other digit counts, such as base 3.

Interviewer cross-questions

Why is exactly one added?

Say: i & (i − 1) removes exactly one 1 bit, so i has one more 1 than the number it maps to.

Is it correct for i = 1?

Say: 1 & 0 = 0, ans[0] = 0, so ans[1] = 1.

Which recurrence would you choose?

Say: Either; the lowest-bit version has one operation fewer per number and no dependence on the parity of i.

Synchronized code walkthrough

Showing: Test 32 positions for every number — shares the player above; click any step to jump.

vector<int> countBits(int n) {
    vector<int> ans;
    for (int i = 0; i <= n; i++) {
        int count = 0;
        for (int b = 0; b < 32; b++) {
            if ((i >> b) & 1) count++;
        }
        ans.push_back(count);
    }
    return ans;
}

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0;
        for (int b = 0; b < 32; b++) {
            if (((i >>> b) & 1) != 0) count++;
        }
        ans[i] = count;
    }
    return ans;
}

def count_bits(n):
    ans = []
    for i in range(n + 1):
        count = 0
        for b in range(32):
            if (i >> b) & 1: count += 1
        ans.append(count)
    return ans

function countBits(n: number): number[] {
  const ans: number[] = [];
  for (let i = 0; i <= n; i++) {
    let count = 0;
    for (let b = 0; b < 32; b++) {
      if ((i >>> b) & 1) count++;
    }
    ans.push(count);
  }
  return ans;
}

vector<int> countBits(int n) {
    vector<int> ans;
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        ans.push_back(count);
    }
    return ans;
}

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        ans[i] = count;
    }
    return ans;
}

def count_bits(n):
    ans = []
    for i in range(n + 1):
        count, x = 0, i
        while x != 0:
            x &= x - 1
            count += 1
        ans.append(count)
    return ans

function countBits(n: number): number[] {
  const ans: number[] = [];
  for (let i = 0; i <= n; i++) {
    let count = 0, x = i;
    while (x !== 0) {
      x &= x - 1;
      count++;
    }
    ans.push(count);
  }
  return ans;
}

vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

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

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

function countBits(n: number): number[] {
  const ans = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
}

vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i & (i - 1)] + 1;
    }
    return ans;
}

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

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

function countBits(n: number): number[] {
  const ans = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i & (i - 1)] + 1;
  }
  return ans;
}