191._number_of_1_bits.md

### 191. Number of 1 Bits

题目:

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


难度:

Easy


转成二进制，数1的个数

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



有wikipedia的题目 [Hamming Weight]((https://zh.wikipedia.org/wiki/汉明重量))



用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代码



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