3.Number of 1 Bits

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.

Solution I: (Using STL)

class Solution
{
public:
    int hammingWeight(uint32_t n)
    {

        bitset<32> b(n);
        int x = b.count();
        return x;
    }
};

Solution II: (Brian Kernighan’s Algorithm)

Algorithm:

Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit.

For example for 4 ( 100) and 16(10000), we get the following after subtracting 3 –> (011 ) , 15 –> (01111)

It integer is not 0 * Do bitwise & with (n-1) and assign the value to n * increment the count by 1.

class Solution
{
public:
    int hammingWeight(uint32_t n)
    {

        int count = 0;
        while (n != 0)
        {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
};

Time Complexity: O(log n)