Solution For Number Of 1 Bits

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)

Step by Step Implementation For Number Of 1 Bits

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>>= 1;
        }
        return count;
    }
}

/*

The above solution is in Java.

We first initialize a count variable to 0. We then iterate through the number until it is equal to 0.

For every iteration, we check if the last bit is 1. If it is, we increment the count variable. Finally, we right shift the number to get rid of the last bit.

At the end, we return the count variable.

class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    //convert the integer to a binary string
    let binary = n.toString(2);
    //count the number of 1's in the string
    let count = 0;
    for(let i = 0; i < binary.length; i++){
        if(binary[i] === '1'){
            count++;
        }
    }
    //return the count
    return count;
};

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

public int HammingWeight(uint n) 
{ 
    int count = 0; 
    while (n > 0) 
    { 
        count += (int) (n & 1); 
        n >>= 1; 
    } 
    return count; 
}