Counting Bits

The Hamming weight (or popcount) of an integer is the number of 1-bits in its binary representation. It appears in checksums, compression, error correction, and bitmask DP. JavaScript has no built-in popcount, but two approaches cover all practical needs.

Brian Kernighan’s Algorithm

The expression n & (n - 1) clears the lowest set bit of n. Repeat until n is zero and count the iterations.

function popcount(n) {
  n = n | 0;   // coerce to int32 — safe for values up to 2^31 - 1
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // clear the lowest set bit
    count++;
  }
  return count;
}

console.log(popcount(0b10110100)); // 4  (bits 2,4,5,7 are set)
console.log(popcount(255));        // 8
console.log(popcount(0));          // 0

Why it works: subtracting 1 from n flips the lowest set bit to 0 and sets all lower bits to 1. ANDing with the original n clears those lower bits, leaving everything above the lowest set bit unchanged. Each iteration removes exactly one set bit, so the loop runs exactly popcount(n) times.

O(n) Table with DP

When you need popcount for every integer from 0 to n, build the table in one pass using a simple recurrence: every integer i has the same set bits as i >> 1, plus 1 if i is odd.

function buildPopcountTable(n) {
  const pc = new Int32Array(n + 1);
  for (let i = 1; i <= n; i++) {
    pc[i] = pc[i >> 1] + (i & 1);
  }
  return pc;
}

const pc = buildPopcountTable(8);
console.log([...pc]); // [0,1,1,2,1,2,2,3,1]

This runs in O(n) time and O(n) space. Each entry is computed from an already- computed entry (i >> 1 < i), so no lookup is ever missing.

Checking Power of Two

Kernighan’s trick also gives a one-liner for power-of-two detection: a power of two has exactly one set bit, so n & (n - 1) equals zero for positive powers of two.

const isPow2 = n => n > 0 && (n & (n - 1)) === 0;
console.log(isPow2(1024)); // true
console.log(isPow2(1000)); // false

Up Next

When integers exceed 32 bits — or even 53 bits — you need BigInt. Learn when to switch and how to use BigInt for modular arithmetic.