Number of 1 bits#

Levels: level-1

Data structures: bits

Practice Link#

Description#

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).

Example#

1Input: 00000000000000000000000000001011
2Output: 3
3Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Python Solution#

 1class Solution(object):
 2    # Use inbuilt functions
 3    def hammingWeightBuiltin(self, n):
 4        """
 5        :type n: int
 6        :rtype: int
 7        """
 8        return bin(n).count('1')
 9
10    # Using bit operation to cancel a 1 in each round
11    # Think of a number in binary `n = XXXXXX1000, n - 1 is XXXXXX0111`.
12    # `n & (n - 1)` will be `XXXXXX0000` which just canceled the last `1`
13    def hammingWeightBitwise(self, n):
14        """
15        :type n: int
16        :rtype: int
17        """
18        c = 0
19        while n:
20            n &= n - 1
21            c += 1
22        return c