DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 968,547 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
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)

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: