DAY 69 - Number of 1 Bits

Welcome to DAY 69. Today we will diverge once again into the Data Structures and look at some more questions. Today we are going to do a question again on Bit Manipulation.

Question: Number of 1 Bits

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

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

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

Algorithm Analysis: Counting Set Bits (Hamming Weight)

Intuition:

The problem requires counting the number of set (1) bits in the binary representation of an unsigned 32-bit integer. Two approaches are provided: a brute-force method and an optimized technique.

Brute-Force Approach:

1. Initialize a counter cnt to keep track of the count of set bits.

2. Iterate through each bit in the binary representation of the given number n:

   • Check if the least significant bit is set (n & 1).
   • If the least significant bit is set, increment the cnt.
   • Right shift n by one bit to move to the next bit.

3. Return the final count cnt.

Code:

int hammingWeight(uint32_t n) {
        int cnt=0;  // stores count
        while(n>0){  
            if((n&1)>0) 
                ++cnt;
            n=n>>1; // shift one bit
        }
        return cnt;

Optimized Approach using Brian Kernighan Algorithm:

1. Initialize a counter count to keep track of the count of set bits.

2. Iterate until all set bits in n are processed:

   • Perform the bitwise AND operation between n and n-1.
   • This operation turns off the rightmost set bit in n.
   • Increment the count.

3. Return the final count.

Code:

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

Complexity Comparison:

Comparison:

The optimized approach using the Brian Kernighan algorithm significantly reduces the number of iterations, making it more efficient. It directly operates on the set bits without traversing through all the bits, resulting in a lower time complexity. This approach is particularly effective when the number of set bits is small compared to the total bits.

In contrast, the brute-force approach iterates through all the bits of the number, leading to a higher time complexity for large numbers.

Overall, the optimized approach is more efficient and performs better in terms of time complexity.