Number Of 1 Bits - Leetcode Solution

Problem statement: Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight)

Example 1: Input: 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2: Input: 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3: Input: 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Solution: The problem can be solved by using bit manipulation techniques.

We can use the following algorithm to count the number of '1' bits.

1. Initialize a count variable to 0.
2. While n is not zero:
     a. If the least significant bit of n is 1, increment the count variable.
     b. Right shift n by 1 bit position.
3. Return the count.

Let's implement the above algorithm in the code:

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

In the above code, we first initialize a count variable to zero. Then we enter a while loop and keep checking if the input number n is not zero. If it is not zero, we check if its least significant bit is 1 or not. If it is 1, we increment the count variable by 1. Finally, we right shift the number by 1 bit position and repeat the above process until the number becomes zero.

Time Complexity: O(log n) Space Complexity: O(1)

1