191 number of 1 bits
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
