Back to solutions

Number of 1 Bits

EasyBit Manipulation

Return the number of set bits (Hamming weight) in the binary representation of an unsigned integer.

Open problem
Constraints
  • The input is a 32-bit unsigned integer

Brian Kernighan's trick

Time O(number of set bits)Space O(1)

n & (n - 1) clears the lowest set bit. Repeat until n is zero, counting iterations, so the loop runs once per set bit rather than 32 times.

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) { n &= n - 1; count++; }
    return count;
}