155. Number of 1 Bits

The expression n & (n - 1) clears the lowest set bit of n. Repeatedly apply it and count how many times you can before n becomes 0 — that count is exactly the number of set bits.

Idea

A naive approach checks all 32 bits. Brian Kernighan's trick is smarter: it does exactly as many iterations as there are set bits.

The key observation: n & (n - 1) removes the lowest set bit of n. Subtracting 1 flips the lowest set bit to 0 and turns every bit below it into 1; ANDing with the original clears that lowest set bit (and the borrow bits) in one step. So each iteration erases one 1-bit.

Algorithm

1. count = 0.
2. While n != 0: do n = n & (n - 1) (erase the lowest set bit) and count += 1.
3. Return count.

Worked example: n = 11 (binary 1011)

n reached 0 after 3 iterations, so 11 has 3 set bits (the 1s in 1011).

Complexity

• Time: O(number of set bits) — at most O(32), and often far fewer.
• Space: O(1).

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