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 set to '1' in its binary representation. This is also known as the Hamming weight.

Example 1:

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

Example 2:

Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Steps:

1. Iterate through bits: We need to examine each bit of the input integer n. We can do this using bit manipulation.

2. Check the least significant bit: The n & 1 operation checks if the least significant bit (LSB) is set (1). If it is, we increment our count.

3. Right shift: The n >>= 1 operation right-shifts the bits of n by one position. This moves the next bit to the LSB position for the next iteration.

4. Repeat: We repeat steps 2 and 3 until all bits have been checked (n becomes 0).

Explanation:

The code efficiently counts the number of set bits by iteratively checking the least significant bit and right-shifting the number. The bitwise AND operation (&) isolates the least significant bit, and the right shift (>>=) moves the bits to the right, allowing us to examine each bit one by one. The loop continues until all bits have been processed (n becomes 0).

Code:

#include <iostream>

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n > 0) {
            count += (n & 1);  // Check and add LSB
            n >>= 1;          // Right shift
        }
        return count;
    }
};

int main() {
    Solution sol;
    uint32_t n1 = 11;  // 1011
    uint32_t n2 = 128; // 10000000
    std::cout << "Number of 1s in " << n1 << ": " << sol.hammingWeight(n1) << std::endl;
    std::cout << "Number of 1s in " << n2 << ": " << sol.hammingWeight(n2) << std::endl;
    return 0;
}

Complexity:

• Time Complexity: O(log n), where n is the input integer. The loop iterates at most 32 times (for a 32-bit integer). The number of iterations is proportional to the number of bits, which is logarithmic in the value of n.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size.