Domain 1EasyCORE

Number of 1 Bits

The problem requires writing a function that counts the number of '1' bits in the binary representation of an unsigned integer. The input is given as an unsigned 32-bit integer, and the output should be the count of '1' bits in its binary form.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

191. Number of 1 Bits

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 0
Acceptance rate: 54.2%


Problem Breakdown

The problem requires writing a function that counts the number of ‘1’ bits in the binary representation of an unsigned integer. The input is given as an unsigned 32-bit integer, and the output should be the count of ‘1’ bits in its binary form.

Inputs:

  • An unsigned 32-bit integer n.

Outputs:

  • An integer representing the number of ‘1’ bits in the binary representation of n.

Implicit Constraints or Tricky Edge Cases:

  • The input is always a 32-bit integer, so we don’t need to handle larger integers.
  • The function should work correctly for both small and large numbers, including edge cases like zero (0) and all ones (0xFFFFFFFF).

Intuition

The brute-force approach would involve converting the integer to its binary string representation and then counting the number of ‘1’ characters. However, this method is inefficient because it involves string conversion and iteration over the entire string.

A better approach leverages bit manipulation. The key insight is that we can use bitwise operations to count the ‘1’ bits directly without converting the number to a string. Specifically, we can repeatedly clear the lowest set bit (i.e., the rightmost ‘1’) using the operation n = n & (n - 1). This operation reduces the number of ‘1’ bits by one each time it is applied. By counting how many times this operation can be performed before n becomes zero, we get the total number of ‘1’ bits.

Approach

We will use a loop to repeatedly clear the lowest set bit in the integer n using the bitwise AND operation n = n & (n - 1). We maintain a counter to keep track of how many times this operation is performed. The loop continues until n becomes zero, at which point the counter will contain the number of ‘1’ bits.

Algorithm Steps:

  1. Initialize a counter count to zero.
  2. While n is not zero:
    • Increment the counter count.
    • Clear the lowest set bit in n using n = n & (n - 1).
  3. Return the counter count.

Complexity Analysis

  • Time Complexity: O(k), where k is the number of ‘1’ bits in the binary representation of n. In the worst case, this is O(32) because there are at most 32 bits.
  • Space Complexity: O(1), as we only use a constant amount of extra space for the counter.

Solution

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

Edge Cases Handled

  • Zero (0): The binary representation of 0 has no ‘1’ bits, so the function returns 0.
  • All ones (0xFFFFFFFF): The binary representation of 0xFFFFFFFF has all 32 bits set to ‘1’, so the function returns 32.
  • Single ‘1’ bit: For numbers like 1, 2, 4, etc., where only one bit is set, the function correctly counts and returns 1.
  • Multiple ‘1’ bits: For numbers with multiple ‘1’ bits, such as 5 (binary 101), the function correctly counts and returns the number of ‘1’ bits.