Leetcode: 191. Number of 1 Bits (Bit manipulation)

Counting Set Bits in a 32-Bit Unsigned Integer - C++ Implementation

Introduction: In this blog post, we'll delve into a C++ solution to count the number of set bits (1s) in a given 32-bit unsigned integer. The task is to efficiently determine the count of set bits in the binary representation of the input number. Understanding this bit manipulation technique can be beneficial in various scenarios, such as optimizing algorithms or solving problems related to binary representations.

Problem Description: The problem can be defined as follows: Given a 32-bit unsigned integer n, we need to count the number of set bits (1s) in its binary representation. For example, for the input n = 11 (binary: 00000000000000000000000000001011), the function should return 3, as there are three set bits in its binary representation.

Approach: To solve this problem, we will implement a function called hammingWeight, which takes a 32-bit unsigned integer n as input and returns the count of set bits.

#include <cstdint>

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

Explanation: Let's break down the implementation step by step:

1. We initialize a variable sum to store the count of set bits and set it to 0 initially.
2. The while loop runs until n becomes 0, which means all bits have been processed.
3. Inside the loop, we increment sum by 1, as we found a set bit (1) in the least significant position.
4. To remove the rightmost set bit in n, we perform bitwise AND operation &= with n - 1. This operation clears the rightmost set bit and maintains the positions of other set bits.
5. The loop continues the process until n becomes 0, effectively counting the number of set bits.
6. Finally, the function returns the computed sum, which represents the count of set bits in the binary representation of the input n.

Example: Let's illustrate the implementation with an example. Consider the input number n = 11:

1. Initially, sum = 0.
2. For the first set bit (1) in n, sum = 0 + 1 = 1.
3. After clearing the rightmost set bit in n, n = 10 (binary: 00000000000000000000000000001010).
4. For the second set bit (1) in n, sum = 1 + 1 = 2.
5. After clearing the rightmost set bit in n, n = 8 (binary: 00000000000000000000000000001000).
6. For the third set bit (1) in n, sum = 2 + 1 = 3.
7. After clearing the rightmost set bit in n, n = 0 (binary: 00000000000000000000000000000000).
8. The loop terminates as n becomes 0, and the function returns sum = 3.

Conclusion: We have successfully implemented a C++ solution to count the number of set bits in a 32-bit unsigned integer. The provided function, hammingWeight, efficiently counts the set bits using a bitwise operation, making it an optimal solution. Understanding this bit manipulation technique can be useful in various programming tasks that involve binary representations and optimizing algorithms. Whether you're working on low-level programming or dealing with binary data, this knowledge can prove invaluable. Happy coding!