DEV Community

Bernice Waweru
Bernice Waweru

Posted on

Number of 1 Bits

Instructions

Approach

There are several ways to solve this problem. Let's look at a few.

Using count()

We convert the decimal number to binary, replace "0b" with no value and count the number of 1's

Implementation

def hammingWeight(self, n: int) -> int:
        bits =  bin(n).replace("0b", "")
        return bits.count('1')

Enter fullscreen mode Exit fullscreen mode

Using the bit_count() method

The method returns the number of ones in the binary representation of the absolute value of the integer.

def hammingWeight(self, n: int) -> int:
        return n.bit_count()
Enter fullscreen mode Exit fullscreen mode

You can review this resource for a better understanding of the method.

Bit Manipulation

We can loop through the number and count the number of 1's
Using the modulus operator(%) we can get the number of 1's and shift n to the right until all 32bits are zeros.

  • n%2 will return 0 or 1 so the count only changes when it is a 1.

Implementation

def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n%2
            n = n >> 1
        return count
Enter fullscreen mode Exit fullscreen mode

This algorithm has a constant time complexity O(1) because we iterate through 32 bits.
The space complexity is O(1) because we do not need extra memory.

I hope you found this helpful. Let me know of other solution approaches.

Top comments (0)