Number of 1 Bits

Difficulty: Easy | Acceptance: 76.80% | Paid: No Topics: Divide and Conquer, Bit Manipulation

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

• Examples
• Constraints
• Approach 1: Loop and Bit Mask
• Approach 2: Brian Kernighan’s Algorithm
• Approach 3: Divide and Conquer (Parallel Counting)

Examples

Input: n = 11 (binary representation: 00000000000000000000000000001011)
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

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

Input: n = 2147483645 (binary representation: 11111111111111111111111111111101)
Output: 30
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty '1' bits.

Constraints

The input must be a binary string of length 32.
0 <= n <= 2³¹ - 1

Approach 1: Loop and Bit Mask

Intuition We can inspect each bit of the integer one by one. By using a bit mask (usually 1), we can check if the least significant bit is set to 1. We then shift the integer to the right to process the next bit.

Steps

• Initialize a counter variable to 0.
• Loop 32 times (since the integer is 32 bits).
• In each iteration, perform a bitwise AND between the number and 1. If the result is 1, increment the counter.
• Right-shift the number by 1 bit to discard the bit we just checked.
• Return the counter.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        for _ in range(32):
            count += n & 1
            n >>= 1
        return count

Complexity

• Time: O(1) — We always iterate 32 times.
• Space: O(1) — We only use a single variable for the count.
• Notes: This is the most straightforward approach but always checks all 32 bits regardless of how many are set.

Approach 2: Brian Kernighan’s Algorithm

Intuition This approach optimizes the loop approach by skipping over the 0 bits. The operation n & (n - 1) flips the least significant 1-bit to 0. We can repeat this operation until the number becomes 0.

Steps

• Initialize a counter variable to 0.
• While n is greater than 0:
  • Perform n = n & (n - 1) to flip the rightmost 1-bit to 0.
  • Increment the counter.
• Return the counter.

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

Complexity

• Time: O(k) — Where k is the number of set bits (1s). In the worst case, it is O(32) or O(1).
• Space: O(1) — Constant space usage.
• Notes: This is generally faster than the loop approach when the number of set bits is small.

Approach 3: Divide and Conquer (Parallel Counting)

Intuition We can count bits in parallel using a divide and conquer strategy. We first count bits in pairs, then aggregate those counts into groups of 4, then 8, 16, and finally 32. This leverages bitwise operations to perform calculations simultaneously across the number.

Steps

• Mask the number to count bits in pairs: n = (n & 0x55555555) + ((n >> 1) & 0x55555555).
• Aggregate pairs into groups of 4: n = (n & 0x33333333) + ((n >> 2) & 0x33333333).
• Aggregate groups of 4 into groups of 8: n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F).
• Aggregate groups of 8 into groups of 16: n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF).
• Aggregate groups of 16 into the final 32-bit count: n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF).
• Return n.

class Solution:
    def hammingWeight(self, n: int) -> int:
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555)
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
        n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
        n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF)
        n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF)
        return n

Complexity

• Time: O(1) — Fixed number of bitwise operations.
• Space: O(1) — No extra space used.
• Notes: This is a highly optimized approach often used in low-level systems programming where performance is critical.