Number of 1 Bits

You are given an unsigned integer n. Return the number of 1 bits in its binary representation.

You may assume n is a non-negative integer which fits within 32-bits.

Approach

Use the bit trick n &= n - 1 to clear the lowest set bit each time. Count how many times this can be done before n becomes zero.

Why It Works

Each operation removes exactly one 1 bit from the binary representation of n. Therefore, the number of iterations equals the number of set bits.

Complexity

• Time: O(k) where k is the number of set bits
• Space: O(1)

Reference Implementation (Python)

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