LeetCode 191. Number of 1 Bits

Problem Overview

The goal is to write a function that takes an unsigned integer and returns the number of ‘1’ bits it has in its binary representation. This value is also known as Hamming weight. This is the classic bit manipulation problem.

Solution 1: Bit-by-Bit Check

Core Idea:

This approach checks each bit of the number individually.

1. Check LSB: Use the bitwise AND operator (n & 1) to check if the Least Significant Bit (LSB) is a 1 . If it is, increment a counter. For example, 5 (101) & 1 (001) results in 1.

2. Right Shift: Shift the number one bit to the right (n >> 1) to discard the LSB and examine the next bit in the following iteration.

3. Repeat: Continue these steps until the number becomes 0.

Time Complexity: O(1), as the loop runs a fixed number of times (32 for a 32-bit integer).

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

Solution 2: Clear Rightmost Set Bit (Optimized)

Core Idea:

This clever approach uses a trick to eliminate one set bit at a time.

1. Key Operation: This operation n & (n - 1) clears the rightmost set bit (’1’) of n. For example, if n is 12 (1100), n-1 is 11 (1011). n & (n - 1) results in 8 (1000), effectively removing the rightmost ‘1’.

2. Count and Repeat: We apply this operation repeatedly and increment a counter each time until n becomes 0. The total count is the number of set bits.

Time Complexity: O(m), where m is the number of set bits. This is highly efficient for numbers with few ‘1’s (sparse numbers).

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