Number of 1 Bits easy

Problem Statement

Write a function that takes an unsigned integer as input and returns the number of bits that are equal to '1' in the binary representation of that integer.

Example 1:

Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The binary representation of 11 is 1011, which has three 1s.

Example 2:

Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The binary representation of 128 is 10000000, which has one 1.

Steps

1. Convert to Binary: While not explicitly required, understanding the binary representation is crucial. You can use built-in methods or manually convert the integer to its binary string representation.

2. Count Set Bits: Iterate through the binary string (or the integer directly using bit manipulation) and count the number of times the bit is '1'.

3. Bit Manipulation (Efficient Approach): A more efficient way involves using bitwise operations. The n & (n - 1) operation clears the least significant set bit in n. By repeatedly applying this until n becomes 0, you can count the number of set bits.

Explanation

The most efficient solution uses bit manipulation. The expression n & (n - 1) cleverly removes the rightmost set bit (1). Let's see how it works:

• Subtracting 1: Subtracting 1 from a number flips all bits from the rightmost 1 to the end, and sets the rightmost 1 to 0.

• Bitwise AND: The bitwise AND operation (&) compares corresponding bits. If both bits are 1, the result is 1; otherwise, it's 0.

Example: Let's say n = 6 (binary 110).

1. n - 1 = 5 (binary 101)
2. n & (n - 1) = 110 & 101 = 100 (binary 4) - The rightmost set bit is cleared.

Repeating this process:

1. n = 4 (binary 100)
2. n - 1 = 3 (binary 011)
3. n & (n-1) = 0 (binary 000)

The loop will run twice, indicating two set bits.

Code (C#)

public class Solution {
    public int HammingWeight(uint n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1); // Clear the least significant set bit
            count++;
        }
        return count;
    }
}

Alternatively, using a loop and string conversion (less efficient):

public class Solution {
    public int HammingWeight(uint n) {
        string binaryString = Convert.ToString((int)n, 2); //Convert to binary string. Cast to int is safe since uint is unsigned.
        int count = 0;
        foreach (char c in binaryString) {
            if (c == '1') {
                count++;
            }
        }
        return count;
    }
}

Complexity

• Time Complexity: O(log n) for the bit manipulation approach. The loop iterates at most log₂(n) times, as each iteration removes at least one set bit. The string conversion approach has a time complexity that depends on the string conversion method which could be considered O(log n) as well.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space. The string method technically uses O(log n) space for the string, but this is still considered relatively efficient compared to the time saved in very large numbers.