Number of 1 Bits — Step-by-Step Visualization

Algorithm Pattern

Bitmasking or Kerninghan's Algorithm

Key Idea

There are two common ways to count set bits: 1. Shift the number one bit at a time and check if the LSB is 1 (`n & 1`). 2. Use Kerninghan's bit trick: `n &= (n - 1)`, which flips the rightmost set bit to 0 in each step. The latter is faster as it only iterates as many times as there are set bits.

Step-by-Step Approach

1. Initialize `count = 0`.
2. While `n` is not 0:
3. Method A: `count += n & 1`, `n >>= 1`.
4. Method B: `n &= (n - 1)`, `count++`.
5. Return `count`.

Common Gotchas

• In JavaScript, bitwise operators operate on 32-bit signed integers. For large numbers or unsigned behavior, use `>>> 1` for logical right shift.