Frontend Beauty
ESC

Type to search the knowledge base.

Counting Bits

Count 1-bits for every number in [0, n] — Brian Kernighan per number, and O(n) DP using i >> 1 and i & 1.

intermediate3 min read
  • dsa
  • bit
  • interview
  • Google
  • Meta
  • Amazon

The problem

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

n = 5 → [0,1,1,2,1,2]
// 0:0, 1:1, 2:10, 3:11, 4:100, 5:101

Brute: popcount each i

function countBitsBrute(n: number): number[] {
  const ans = new Array<number>(n + 1);
  for (let i = 0; i <= n; i++) {
    let x = i;
    let c = 0;
    while (x) {
      x &= x - 1; // clear lowest set bit
      c++;
    }
    ans[i] = c;
  }
  return ans;
}
Time O(n · α) α = bits set ≤ 32
Space O(1) extra

Brian Kernighan is already solid. Interviewers often want the linear DP insight.

Optimal DP: reuse smaller answers

  • ans[i] = ans[i >> 1] + (i & 1)
    Right-shift drops LSB; add 1 if LSB was set.

  • Or: ans[i] = ans[i & (i-1)] + 1
    Clear lowest set bit, then +1.

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;
}

function countBitsAlt(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;
}
Time O(n)
Space O(n) for output

Table

i bin ans
0 0 0
1 1 1
2 10 1
3 11 2
4 100 1
5 101 2

Edge cases

  • n = 0 → [0]
  • Large n (LC ≤ 10^5) — O(n) fine
  • Don’t use String(i.toString(2)) in interviews unless joking

Common mistakes

  • Sign-bit issues — here non-negative only
  • i/2 float in languages without integer division — use >> or Math.floor
  • Off-by-one array length n instead of n+1

Interview delivery

  1. Popcount definition.
  2. Kernighan loop per i.
  3. DP recurrence with shift.
  4. O(n).

Mental model

Popcount is a building block for bit DP, chess bitboards, and permission flag UIs. Computing each independently is fine; the interview win is noticing i and i>>1 differ by only the least bit.

Implementation notes for JS

  • number is IEEE-754 double; bitwise ops coerce to int32. For n up to 1e5 in this problem you’re safe with >> and &.
  • Prefer i >> 1 over Math.floor(i/2) for clarity in bit problems.
  • Don’t use n.toString(2).split('1').length-1 as your main solution.

Out-loud answer

“ans[i] is hamming weight of i for 0..n. Brian Kernighan per value is O(n·bits). Better: DP ans[i]=ans[i>>1]+(i&1) in O(n). Space O(n) for the answer array.”

Further reading