Skip to main content

🟩 Number of 1 Bits (#191)

🔗 Problem Link​

📋 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).

💡 Examples​

Example 1​

Input: n = 00000000000000000000000000001011
Output: 3

Example 2​

Input: n = 00000000000000000000000010000000
Output: 1

🔑 Key Insights & Approach​

Core Observation: Use n & (n-1) to remove rightmost 1 bit, or check each bit.

Why n & (n-1)?

  • O(number of 1 bits) time
  • Removes rightmost 1 each iteration
  • Efficient bit manipulation trick

Pattern: "Bit Counting" pattern.

🐍 Solution: Python​

Approach: n & (n-1) Trick​

Time Complexity: O(number of 1s) | Space Complexity: O(1)

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

Approach 2: Check Each Bit​

Time Complexity: O(32) = O(1) | Space Complexity: O(1)

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

🔵 Solution: Golang​

Approach: n & (n-1)​

Time Complexity: O(number of 1s) | Space Complexity: O(1)

func hammingWeight(num uint32) int {
    count := 0
    for num != 0 {
        num &= num - 1
        count++
    }
    return count
}

📚 References​