Number of 1 Bits | LeetCode 191 | Python | Solution

To solve this ‘number of 1 bits‘ problem, we have to count the number of ‘1’ bits from an unsigned integer. It’s an easy problem if you know about bit manipulation. Let’s see how we can solve it.

LeetCode 191

Mainly we will use ‘>>‘ (shift right) to solve this problem. Shift right is one of the most common bitwise operators. It moves the bit values to the right. Let’s see the following example.

1100100 >> 1 (number of bits we want to shift to the right)
1100100 >> 1 = 0110010
0110010 >> 1 = 0011001
0011001 >> 2 = 0000110

Using this operator, we can come up with a solution. But first, we need to run a loop until there are no 1s in the given unsigned integer. And in the loop, we will check whether the rightmost bit is ‘1’ or not. We can check this using the % operator (n % 2). If the value is 1, we will increment the final count by 1. As we apply it to a binary number, the result of n % 2 is either 1 or 0, and we can increase the count by default from it.

And then, we will shift the unsigned integer value to 1 step right by using >> (n >> 1). The loop will continue if there is any ‘1‘ left.

We will do it until there is no ‘1’ left. And finally, we will return the total count.

I think the solution in code can give you a better understanding than my vague explanation :). Let’s see.

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        count = 0

        while n:
            count += n % 2
            n = n >> 1
        
        return count

The time complexity of this solution is O(32), which we can write as O(1). As we know from the problem description, the length of the given unsigned integer will be 32. So the loop will run at most 32 times.

Tags: LeetCodeProblem SolvingPython