HARD Lab · Binary · 22

191. Number of 1 Bits

Count the 1-bits in a 32-bit integer using Brian Kernighan's trick: n & (n − 1) clears the lowest set bit in one operation, so the loop runs exactly as many times as there are set bits — far fewer iterations than checking all 32 positions.

● EasyBit ManipulationTypeScript

PROBLEM What we're solving

Return the number of 1 bits (the Hamming weight / population count) in the binary representation of a non-negative integer. n = 11 is 1011 in binary, so the answer is 3. n = 128 is 10000000 — exactly one set bit — so the answer is 1.

KEY IDEA n & (n − 1) always clears exactly the lowest set bit

Insight → subtracting 1 from n flips the lowest set bit to 0 and sets every trailing 0 to 1. AND-ing back with n zeroes out those trailing bits and preserves everything above. One iteration = one 1-bit removed. Count iterations to count bits — the loop runs exactly k times for an integer with k set bits.

RECIPE Brian Kernighan — clear bits, count steps

  • 0 · Initialise. Set count = 0.
  • 1 · Loop while n ≠ 0. As long as any set bit remains, there is work to do.
  • 2 · Clear lowest bit: n = n & (n − 1). This is the whole trick. One AND clears exactly one 1-bit, no matter which position it occupies.
  • 3 · Increment count. Each iteration corresponds to one cleared bit.
  • 4 · Return count. When n = 0 the loop exits; count holds the answer.
Classic confusion → beginners write n & 1 to test the LSB, then n >>>= 1to right-shift — correct but always loops 32 times. Kernighan's trick loops only k times (k = set bits), which matters when k ≪ 32.

COST Complexity & alternatives

Check each of 32 bits
O(32) = O(1)
Always 32 iterations, regardless of how many bits are set.
Brian Kernighan
O(k)
k = popcount. Best case 0 iterations, worst case 32.

Both are technically O(1) for a fixed-width integer, but Kernighan is faster in practice for sparse bit patterns. The built-in Math.clz32 / CPU popcnt instruction is the real-world constant-time answer.

Pattern transfer → the same n & (n − 1) idiom appears in Power of Two (exactly one bit set → n & (n − 1) === 0), Counting Bits (fill a DP table using it as a recurrence), Hamming Distance (XOR then count), and Reverse Bits.

RUN IT Clear lowest set bit with n & (n−1), count iterations

step 0 / 7
STARTn = 11 in binary: 1011. We use Brian Kernighan's trick: each n & (n − 1) clears the lowest set bit in one step.
n bits13021110
State
1011(11)
n
—
n − 1
0
count
lowest set bit (about to clear)other set bitsn−1 (mask)count updated
slowfast

TYPESCRIPT The solution, annotated

hammingWeight.ts
function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1);   // clear the lowest set bit
    count++;
  }
  return count;
}

Reading it block by block

Line 2 — counter. count accumulates one increment per set bit found. Initialise to 0 before the loop.
Line 3 — loop condition. n !== 0 exits as soon as all bits are cleared. For n = 0, the body never executes and we correctly return 0.
Line 4 — the trick. n & (n - 1) clears the lowest set bit. Why? Subtracting 1 from n flips its LSB from 1 to 0 and sets all trailing zeros to 1. AND-ing with the original n zeroes those bits and leaves everything above the LSB intact. One operation, one bit gone.
Line 5 — count it. Every iteration corresponds to exactly one 1-bit being cleared, so incrementing here is correct.
Line 7 — return. Loop exits when n === 0; return the tally. Contrast with the naive approach: while (n) {count += n & 1; n>>> = 1; } — it always executes 32 iterations.
Complexity → O(k) time where k is the number of set bits (≤ 32). O(1) space. For a fixed 32-bit word the naive bit-by-bit scan is also O(1), but Kernighan's version terminates after k iterations which is strictly fewer when k < 32.

INTERVIEWFollow-ups they'll ask

  • "What if the input can be a 64-bit integer?" The same loop works — just treat the value as a JS BigInt and adjust the !== 0n / n & (n - 1n) operations.
  • "Can you do it in O(1) with a lookup table?" Pre-compute popcount for all 8-bit values (256 entries), then sum four byte slices of the 32-bit word. Constant memory, extremely fast.
  • "How does this relate to Power of Two?" A power of two has exactly one set bit, so n > 0 && (n & (n - 1)) === 0 is the classic O(1) test.
  • "Counting Bits follow-up: fill bits[0..n] for all n?" Use the DP recurrence bits[i] = bits[i >> 1] + (i & 1) — each entry derived in O(1) from a previously computed one.
  • "Hamming Distance between two numbers?" XOR the two integers to isolate differing bits, then apply this function to the XOR result.

MNEMONIC The one-liner

"n & (n-1) shaves off the last whisker — count the shaves until the face is bare."

TRIGGERS When you see ___ → reach for ___

"count set bits / 1-bits / popcount"n & (n-1) loop, k iterations
"is n a power of two?"n > 0 && (n & (n-1)) === 0
"Hamming distance between a and b"hammingWeight(a ^ b)
"fill bits[0..n] for all n"DP: bits[i] = bits[i>>1] + (i & 1)

SKELETON The reusable shape

skeleton.ts
let count = 0;
while (n !== 0) {
  n = n & (n - 1);  // clear lowest set bit
  count++;
}
return count;

FLASHCARDS Tap to flip

What does n & (n − 1) do?
Clears the lowest (least significant) set bit of n, leaving all other bits unchanged.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
How many iterations does the Brian Kernighan loop run for n = 11 (binary 1011)?
QUESTION 02
What does n & (n − 1) do?
QUESTION 03
What expression efficiently tests whether n is a power of two?
QUESTION 04
Time complexity of Brian Kernighan for a 32-bit integer (k set bits)?
QUESTION 05
How do you compute the Hamming Distance between integers a and b using hammingWeight?
QUESTION 06
The Counting Bits problem asks for bits[0..n] in O(n) time. Which recurrence is correct?
QUESTION 07
For n = 0, what does hammingWeight return?