Number of 1 Bits

Problem

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Example 1:

Input: n = 11
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three set bits.

Example 2:

Input: n = 128
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one set bit.

Example 3:

Input: n = 2147483645
Output: 30
Explanation: The input binary string 01111111111111111111111111111101 has a total of thirty set bits.

Constraints:

1 <= n <= 2^31 - 1

Follow up: If this function is called many times, how would you optimize it?

Solution

Approach 1: Loop and Check Rightmost Bit

The key insight is to repeatedly check the rightmost bit and shift right.

Implementation

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1  # Check if rightmost bit is 1
            n >>= 1         # Right shift by 1
        return count

Approach 2: Brian Kernighan’s Algorithm

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1  # Clear the rightmost set bit
            count += 1
        return count

Approach 3: Using Built-in

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

Approach 4: Lookup Table (For Optimization)

class Solution:
    # Precomputed lookup table for 8-bit numbers
    lookup = [0] * 256

    def __init__(self):
        # Build lookup table on first instantiation
        if Solution.lookup[0] == 0 and Solution.lookup[1] == 0:
            for i in range(256):
                Solution.lookup[i] = (i & 1) + Solution.lookup[i // 2]

    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += Solution.lookup[n & 0xFF]  # Process 8 bits at a time
            n >>= 8
        return count

Complexity Analysis

Loop and Check:

Time Complexity: O(log n) or O(32) for 32-bit integers. Number of iterations equals number of bits.
Space Complexity: O(1)

Brian Kernighan’s Algorithm:

Time Complexity: O(k), where k is the number of set bits. More efficient when few bits are set.
Space Complexity: O(1)

Lookup Table:

Time Complexity: O(1) per lookup, O(log n / 8) overall
Space Complexity: O(256) for the lookup table

Key Insights

Rightmost Bit Check: Use n & 1 to check if the rightmost bit is 1.
Right Shift: Use n >>= 1 to move to the next bit.
Brian Kernighan’s Trick: n & (n-1) clears the rightmost set bit. This is faster when there are few set bits.
How n & (n-1) Works:
- Example: n = 12 (1100), n-1 = 11 (1011)
- n & (n-1) = 1100 & 1011 = 1000
- The rightmost 1 bit is cleared
Optimization for Repeated Calls: Use lookup table to process multiple bits at once.
Hamming Weight: This problem computes the Hamming weight (population count) of a number.
Alternative Names: Also called popcount, sideways sum, or bit summation.