LeetCode #191: Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/description/

The problem “Number of 1 Bits” requires us to count the number of 1 bits in an unsigned integer. In other words, we need to determine the number of positions where the binary representation of the number has a 1.

Here is how we can solve the problem:

1. We can use a bitwise AND operator to check if the rightmost bit is a 1 or not. If it is, we increment a counter.
2. Then, we shift the number one bit to the right, which effectively drops the rightmost bit.
3. We repeat steps 1 and 2 until the number becomes 0.

Using the above approach, we can determine the number of 1 bits in an unsigned integer.

Here is the Python solution to the problem:

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

Time and Space Complexity

The time complexity of this solution is O(log n), since we need to shift the bits of the number until it becomes 0. The space complexity is O(1), since we only use a constant amount of extra space to store the count variable.