Number of 1 Bits

Problem (restated)

Return the number of set bits (Hamming weight) in a 32-bit integer.

Intuition

n &= n-1 clears the lowest set bit; count until n=0.

Approaches

export function hammingWeight(n: number): number {
  let c = 0;
  n >>>= 0;
  while (n) {
    n &= n - 1;
    c++;
  }
  return c;
}

export function hammingWeight(n: number): number {
  let c = 0;
  n >>>= 0;
  while (n) {
    n &= n - 1;
    c++;
  }
  return c;
}

Template connection

Bit manipulation set-bit checks.

Reflection

• n &= n - 1 clears the lowest set bit. The number of loops is the number of 1 bits.
• A Python negative never runs out of bits. This value is an unsigned 32-bit word.
• 0 answers 0. The single bit at 2**31, read as unsigned, counts as 1.