Problem Statement

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

For example, the 32-bit integer 11 has binary representation 00000000000000000000000000001011, so the function should return 3.

Additional information

• The input must be a non-negative integer.
• The input represents a signed or unsigned integer (in Python, integers have arbitrary precision, but we treat n as the value itself).

Brian Kernighan's Algorithm

Intuition

There are two main ways to solve this.

Approach 1: Modulo and Shift
Loop through the bits. Check if the last bit is 1 (n % 2 or n & 1). Then shift n to the right by 1 (n = n >> 1). Repeat until n becomes 0.

Approach 2: Brian Kernighan's Algorithm (Optimal)
This is a neat bit manipulation trick.

• The operation n & (n - 1) always removes the lowest set bit (turns the rightmost 1 into a 0).
• We can run a loop: while n > 0, perform n = n & (n - 1) and increment a counter.
• This is faster because it only loops as many times as there are 1s, instead of looping for every single bit (e.g., 32 times).

Algorithm

Step 1: Initialize a counter count = 0.

Step 2: Start a loop that runs while n is non-zero.

Step 3: Inside the loop, perform the magic operation: n = n & (n - 1).

• Example: 1100 (12) -> 1100 & 1011 -> 1000 (8). (One 1 removed).

Step 4: Increment count by 1.

Step 5: When n becomes 0, return count.

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

Time & Space Complexity

• Time Complexity: O(1). Specifically O(k), where k is the number of set bits. Since standard integers are fixed size (e.g., 32 or 64 bits), this is considered constant time O(1).
• Space Complexity: O(1).