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:
- Initialize a counter
countto zero. - While
nis not zero:- Increment the counter
count. - Clear the lowest set bit in
nusingn = n & (n - 1).
- Increment the counter
- 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 of0has no ‘1’ bits, so the function returns0. - All ones (
0xFFFFFFFF): The binary representation of0xFFFFFFFFhas all 32 bits set to ‘1’, so the function returns32. - Single ‘1’ bit: For numbers like
1,2,4, etc., where only one bit is set, the function correctly counts and returns1. - Multiple ‘1’ bits: For numbers with multiple ‘1’ bits, such as
5(binary101), the function correctly counts and returns the number of ‘1’ bits.