Count set bits

Count the 1s in the binary form of a number. One loop iteration per set bit, not per bit.

The idea

Subtracting 1 flips the lowest set bit to 0 and every bit below it to 1. ANDing with the original keeps everything above that bit and wipes the rest, so exactly one 1 disappears per step.

Code

int countBits(unsigned int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1; // clears the lowest set bit
        count++;
    }
    return count;
}

def count_bits(n: int) -> int:
    count = 0
    while n:
        n &= n - 1  # clears the lowest set bit
        count += 1
    return count

public static int CountBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1; // clears the lowest set bit
        count++;
    }
    return count;
}

Tips

• n & (n - 1) == 0 is the classic test for a power of two.
• This is Brian Kernighan's trick.

In the .NET library

System.Numerics.BitOperations.PopCount(uint) does this with a single CPU instruction. Use it in real code.