Leetcode

191. Number of 1 Bits

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

Example 1:

1
2
3
4
> Input: 11
> Output: 3
> Explanation: Integer 11 has binary representation 00000000000000000000000000001011 
>

Example 2:

1
2
3
4
> Input: 128
> Output: 1
> Explanation: Integer 128 has binary representation 00000000000000000000000010000000
>

Method1

1
2
3
4
5
6
7
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count("1")

Method2

思路：

Int一共32为，每位数字检验是否为1

具体操作：检验最后一个数字，检验完右移，一共32次

Code

1
2
3
4
5
6
7
class Solution(object):
    def hammingWeight2(self, n):
        ans = 0
        for i in range(32):
            ans += n & 1
            n >>= 1
        return ans

Method3

原理：

N = N & (N-1)可以消除N的二进制表示的最后一个1

N N-1 N & (N-1)
1011 1010 1010
1010 1001 1000
1000 0111 0000

Code

1
2
3
4
5
6
7
class Solution(object):
	def hammingWeight3(self, n):
        count = 0
        while n != 0:
            n = n & (n-1)
            count +=1
        return count