191._number_of_1_bits.md

191. Number of 1 Bits

题目:

https://leetcode.com/problems/number-of-1-bits/

难度:

Easy

转成二进制，数1的个数

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count('1')

有wikipedia的题目 Hamming Weight

用wikipedia的解法：

原理是在于每次使用x & x-1 总会把低位的数字给置0

比如 3 = 011 2 = 010 3 & 2 = 010 cnt =1

​ 2 = 010 1 = 001 2 & 1 = 000 cnt = 2

比如 9 = 1001 8 = 1000 9&8 = 1000 cnt =1

​ 8 = 1000 7 = 0111 8&7 = 0000 cnt = 2

减1操作将最右边的符号从0变到1，从1变到0，与操作将会移除最右端的1。如果最初X有N个1，那么经过N次这样的迭代运算，X将减到0。下面的算法就是根据这个原理实现的。

所以关键点是每次都会把最右边的1变成0.

AC代码

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        cnt = 0
        while n != 0:
        	n &= n - 1
        	cnt += 1
        return cnt