Number of 1 Bits

easy bit manipulation

Problem

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Inputn = 0b00000000000000000000000000001011

Output3

Brian Kernighan: n & (n − 1) clears the lowest set bit. Each iteration removes one 1-bit, so the loop runs exactly popcount(n) times.

n (decimal, 0 ≤ n < 2^32)

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }
}

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

Explanation

We need to count how many 1 bits a number has. The naive way is to check all 32 bit positions, but there is a slicker trick that only does as much work as there are set bits.

The key fact is Brian Kernighan's trick: the expression n & (n - 1) always clears the lowest set bit of n. Subtracting 1 flips that lowest 1 to 0 and turns all the zeros below it into ones; ANDing with the original wipes that bit out.

So each time we run n &= n - 1 we remove exactly one 1 bit and add 1 to count. We loop while n is not zero, and the number of loops is exactly the number of set bits.

Example: n = 11 = 1011. First step gives 1010, then 1000, then 0000 — three steps, so the answer is 3.

This is faster than scanning every bit because it skips straight from one set bit to the next.

Time: O(popcount(n)) Space: O(1)