1. 题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
2. 题目分析
-
主要算法：对于二进制数
，
操作相当于去掉
是逻辑运算与，例子：
n = 0100100
n-1 = 0100011
n & (n-1) = 0100000 # 相较于0100100 从右起第一个1去掉了
- 故求
做与运算
- 对于负数
，计算机运算有以下几个原则：
- 都以补码的形式，进行加法运算
- 所得结果也为补码
- 如果是负数，运用上述算法运算，最终定会得到
&
即
做与运算，答案始终为
，即
- 综上代码应考虑负数情况，将其补码最高位经过转换后变为0，而其他位不变，这意味着计数的时候需要再加上1
3. 代码
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
if n < 0:
n = n & 0xffffffff
count = 0
while n: # 循环终止的条件是为0
count += 1
n = n&(n-1)
return count
