DAY 69 - Number of 1 Bits
Tags: leetcode, algorithms, coding, tutorial
Published: 2023-08-11 19:36:01



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](https://leetcode.com/problems/number-of-1-bits/description/)

_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:

| Approach | Time Complexity | Space Complexity |
|----------|-----------------|------------------|
| Brute-Force | O(log n) | O(1) |
| Optimized | O(k), where k is the number of set bits | O(1) |

### 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.