Solution Explanation for Number of 1 Bits

This problem asks to count the number of set bits (1s) in the binary representation of a given integer. We'll explore two efficient solutions.

Solution 1: Brian Kernighan's Algorithm

This approach cleverly uses bit manipulation to count set bits. The core idea is to repeatedly remove the least significant set bit until no set bits remain.

Algorithm:

1. Initialization: Initialize a counter ans to 0.
2. Iteration: While n is not 0:
   • n &= n - 1: This operation clears the least significant set bit in n. For example, if n is 6 (binary 110), n - 1 is 5 (binary 101), and the bitwise AND results in 4 (binary 100), effectively removing the rightmost 1.
   • ans += 1: Increment the counter.
3. Return: Return ans.

Time Complexity: O(k), where k is the number of set bits in n. In the worst case (n is a power of 2), k is 1. On average, k is log₂(n). This is significantly better than iterating through all bits (O(log₂(n)) in the worst case).

Space Complexity: O(1), as we use only a few constant extra variables.

Solution 2: Using n & -n

This solution leverages the property that n & -n isolates the least significant set bit of n. Subtracting this bit from n effectively removes it.

Algorithm:

1. Initialization: Initialize a counter ans to 0.
2. Iteration: While n is not 0:
   • n -= (n & -n): Subtract the least significant set bit from n.
   • ans += 1: Increment the counter.
3. Return: Return ans.

Time Complexity: Same as Solution 1: O(k), where k is the number of set bits.

Space Complexity: O(1).

Code Examples (Python and Java):

Solution 1 (Brian Kernighan's Algorithm):

Python:

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            n &= n - 1
            ans += 1
        return ans
 

Java:

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

Solution 2 (Using n & -n):

Python:

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            n -= n & -n
            ans += 1
        return ans

Java:

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

Both solutions are highly efficient for counting set bits, particularly when dealing with numbers having a relatively small number of set bits. The provided code snippets show implementations in various programming languages. The uint32_t type in C++ ensures that we're treating n as an unsigned 32-bit integer, handling the problem's constraints correctly. Other languages handle this implicitly or through similar unsigned integer types. The Rust solution directly utilizes the built-in count_ones() method for optimal efficiency in that language.