191. Number of 1 Bits

Description

The hammingWeight function calculates the number of '1' bits in the binary representation of a given integer n. This function is often referred to as the "population count" or "bit count".

Intuition

The intuition behind the hammingWeight function is to repeatedly check the least significant bit of the integer and shift the integer to the right until all bits have been processed. By counting how many times the least significant bit is '1', we can determine the number of '1' bits in the binary representation of the integer.

Approach

1. Initialize a counter count to zero. This counter will keep track of the number of '1' bits.
2. Use a loop to iterate over all bits in the integer n.
3. In each iteration, check if the least significant bit is '1' using the bitwise AND operation n & 1. If it is, increment the count.
4. Perform an unsigned right shift on the integer n to process the next bit. In Python, you can achieve this by using the expression n >>= 1.
5. Continue the loop until all bits have been processed (i.e., until n becomes zero).
6. Return the count as the result.

Complexity

Time Complexity:

O(1) - The function always processes 32 bits (for a 32-bit integer), so the time complexity is constant.

Space Complexity:

O(1) - The function uses a constant amount of space regardless of the input size.

Code

C++

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

Python

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

Java

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

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function (n) {
    let count = 0;
    while (n !== 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;

};