Problem #191: Number of 1 Bits

Intuition & Strategy Breakdown

Use Brian Kernighan's bit manipulation algorithm (n = n & (n - 1)) to clear the lowest set bit in O(set bits) operations.

Python Solution

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= (n - 1)
            count += 1
        return count

Java Solution

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