题解 | 二进制中1的个数

方法一：检查二进制每一位数字

我们通过右移操作消除第 i 位右边的数字，通过与 1 操作消除第 i 位左边的所有数字，对数字 n 重复32次这种操作就可以求得每一位的数字。
当我们要提取从右往左数第3位数字时：

c++代码如下：

class Solution {
public:
     int  NumberOf1(int n) {
         int res = 0;
         for (int i = 0; i < 32; i++)
             res += (n >> i) & 1;
         return res;
     }
};

python3解法思路相同，

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        res = 0
        for i in range(32):
            res += (n >> i) & 1
        return res

方法一切记不要只通过 >> 运算符进行操作，因为负数的右移操作会在数字最左端补 1 ，导致 n 始终不为0，造成无限循环。

方法二：通过位运算公式 n & (n - 1)

公式 n & (n - 1) 的作用是使 n 的二进制形式的最右边一个数字 1 变成 0，重复计算的效果如下，最后得到 0：

每消除一个 1 计数一次，直到 n 变成 0，最后得到的计数就是 1 的个数。

class Solution {
public:
     int  NumberOf1(int n) {
         int res = 0;
         for (; n; n &= n - 1, res++);
         return res;
     }
};

python3与c++不同之处在于，c++中因为 n 是 32 位整数，所以当 n 为 -2147483648 时再减 1 会导致负数溢出（int 的范围是 [-2 ^ 31, 2 ^ 31 - 1]），溢出之后得到正数与运算结果为 0 不会导致死循环。但是 python 中的数字没有大小限制，在循环中减 1 后 n 依然为复数，n 始终不为 0 导致死循环。所以在 python 中需要先把 n 取成大正数。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        res = 0
        if n < 0: n &= 0xffffffff
        while n:
            res += 1
            n &= n - 1
        return res

由于输入数字的长度始终不超过32位，所以两种算法的时间复杂度是 O(1)