LeetCode Solution 191 - Number of 1 Bits

Problem Statement

Given an unsigned integer, return the number of 1 bits it has (also known as the Hamming weight).

Example 1:

Input:

n = 00000000000000000000000000001011

Output:

3

Explanation:

The input binary string 00000000000000000000000000001011 has three 1 bits.

Example 2:

Input:

n = 00000000000000000000000010000000

Output:

1

Example 3:

Input:

n = 11111111111111111111111111111101

Output:

31

Explanation:

The input binary string 11111111111111111111111111111101 has thirty-one 1 bits.

---

Optimal Approach: Bit Manipulation

Why Bit Manipulation?

• Using bitwise operations, we can efficiently count the number of 1 bits.
• n & (n - 1) removes the rightmost 1 bit in each step, reducing the number of operations.
• This method runs in O(k), where k is the number of 1 bits.

Algorithm:

1. Initialize a counter to 0.
2. While n is nonzero:
   • Increment the counter.
   • Update n = n & (n - 1), removing the rightmost 1 bit.
3. Return the counter as the final result.

---

C++ Code Implementation

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
};

---

Step-by-Step Explanation

1. Initialize count = 0.
2. Loop until n == 0:
   • n & (n - 1) removes the rightmost 1 bit.
   • Increment count for each 1 bit removed.
3. Return count as the number of 1 bits.

---

Dry Run

Input:

n = 00000000000000000000000000001011

Execution:

Step	n (Binary)	Count	n & (n - 1)
1	00000000000000000000000000001011	1	00000000000000000000000000001010
2	00000000000000000000000000001010	2	00000000000000000000000000001000
3	00000000000000000000000000001000	3	00000000000000000000000000000000
Result	00000000000000000000000000000000	3	-

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Iterative Bit Check	O(32)	O(1)	Inefficient for large inputs
Look-up Table	O(1)	O(256)	Requires precomputed table
Bit Manipulation (Best)	O(k)	O(1)	Fast and space-efficient

---

Complexity Analysis

• Time Complexity: O(k), where k is the number of 1 bits in n.
• Space Complexity: O(1), using only a few variables.

---

Conclusion

• Best Approach: Bit Manipulation using n & (n - 1).
• Further Practice:
  • Counting Bits
  • Power of Two
  • Reverse Bits

This solution efficiently computes the Number of 1 Bits using Bitwise Operations, making it optimal for large numbers.