Frontend Beauty
ESC

Type to search the knowledge base.

Number of 1 Bits

Hamming weight — count set bits with n & (n-1) Brian Kernighan, or shift-and-mask, O(set bits).

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

The problem

Given an unsigned integer n (as number), return the number of 1 bits in its binary representation (Hamming weight).

Input:  n = 11   // 1011
Output: 3

Input:  n = 128  // 10000000
Output: 1

In JS interviews, treat n as a 32-bit unsigned value when the problem says so (n >>> 0).

Brute force

Check each of 32 bits.

function hammingWeightBrute(n: number): number {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    if ((n & (1 << i)) !== 0) count++;
  }
  return count;
}

Careful: 1 << 31 is negative in JS signed 32-bit ops. Prefer n & 1 with unsigned shift:

function hammingWeightShift(n: number): number {
  let count = 0;
  n = n >>> 0; // force uint32
  while (n) {
    count += n & 1;
    n >>>= 1;
  }
  return count;
}
Time O(32) = O(1) word size
Space O(1)

Optimal: Brian Kernighan

n & (n - 1) clears the lowest set bit. Loop until zero — iterations = number of ones.

function hammingWeight(n: number): number {
  let count = 0;
  n = n >>> 0;
  while (n) {
    n &= n - 1;
    count++;
  }
  return count;
}
Time O(k) where k = number of set bits
Space O(1)

Also valid: n.toString(2).split("1").length - 1 — not what they want for bit-manipulation rounds.

Edge cases

  • n = 0 → 0
  • All bits set (0xffffffff) → 32
  • Powers of two → 1
  • JS signed vs unsigned: use >>>

Common bugs

  • Arithmetic >> sign-extending forever on negatives
  • Infinite loop if you use >> on high bit set
  • Counting only until n becomes 0 without unsigned semantics on negative inputs

Interview delivery

  1. Hamming weight definition.
  2. Mention 32-bit loop, then Kernighan.
  3. Code n &= n-1.
  4. Discuss JS >>> 0.
  5. Follow-up: Counting Bits.

Kernighan step example

n = 12 (1100):

  • 12 & 11 = 8 (1000), count 1
  • 8 & 7 = 0, count 2

Two iterations, two set bits. A 32-iteration loop would still work but does more work on sparse numbers.

JS signed trap

If n is passed as signed and the high bit is set, n >> 1 sign-extends (fills 1s) and can loop forever. Always prefer >>> for logical shifts, or force n >>> 0 first.

Built-ins

Number.prototype.toString(2) counting ones is fine for scripts, weak for bit-manipulation interviews. Mention it only as a one-liner check for tests.

Further reading