Number of 1 Bits

Count the set bits in an integer.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Number of 1 Bits: Each value & (value - 1) update removes one lowest set bit, so the number of loop iterations is the Hamming weight.

Input and goalCount the set bits in an integer.

Initialize value and countFor value 45 = 00101101, count starts at 0 and the lowest set bit is at bit position 0.

00011203141506lowest 117

value45count0loopCondition45 != 0

Recognize it

The task asks for the population count of an integer, and work should scale with the number of 1 bits rather than the fixed bit width.

Keep true

After count iterations, count equals the number of 1 bits removed from the original value, and the current value contains every original set bit not yet removed.

Reuse it

Use x & (x - 1) whenever progress is defined by deleting one set bit; related uses include power-of-two tests, iterating subsets, and finding the lowest set-bit contribution.

Pattern: Remove one set bit at a time.

Simple idea: value & (value - 1) changes the lowest 1 bit to 0. Count how many times this can happen.

def hamming_weight(value: int) -> int:
   count = 0
   while value:
      value &= value - 1
      count += 1
   return count

Cost: $O(b)$ time and $O(1)$ space, where $b$ is the number of set bits.