Number of 1 Bits

def hammingWeight(n):
    count = 0
    while n:              # pins left
        n &= n - 1        # knock out the lowest pin
        count += 1        # one roll
    return count

Number of One Bits. Given a positive integer, count the ones in its binary form. That count is called its Hamming weight.

Take eleven. In binary, that's one, zero, one, one. Stand a bowling pin on every one bit. Three pins, so the answer is three.

The simple way checks one bit at a time. Read the last bit with n AND one, add it to the count, shift n right, and repeat. That walks every position up to the highest pin: up to thirty-two steps, even for a single pin.

Brian Kernighan's trick skips the empty spots. Subtracting one flips the lowest one bit to zero, and turns every zero below it into a one. Take twelve: one, one, zero, zero. Minus one gives one, zero, one, one. AND the two, and the lowest pin is gone, while everything above it stays.

So the code is one short loop. While n is not zero, set n to n AND n minus one, and add one to the count. Every roll knocks out exactly one pin.

Back to eleven. Roll one: one, zero, one, one becomes one, zero, one, zero. Roll two: one, zero, zero, zero. Roll three: zero. The lane is clear after three rolls, so the answer is three. Now try one hundred twenty-eight. One pin, one roll, where bit by bit takes eight shifts.

The loop runs once per one bit, so the time is the number of set bits, at most thirty-two: constant for a fixed-size integer. The space is constant too.

Subtract one, AND, count the roll. That's Number of One Bits.