题目描述

输入一个32位整数，输出该数二进制表示中1的个数。

样例

样例1

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

样例2

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。

算法1

(位运算) $O(logn)$

在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致 nn 永远不为0，就死循环了。
解决办法是把 nn 强制转化成无符号整型，这样 nn 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。

C++ 代码

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int un = n; // c++中使用unsigned int可以在高位补0,避免死循环
        while (un) res += un & 1, un >>= 1;
        return res;
    }
};

算法2

(位运算) $O(M)$

M为n对应二进制1的个数

class Solution {
public:
    int NumberOf1(int n) {
        int count = 0;
        while (n)
        {
             n = n & (n - 1); // 将n最右边一个1变为0,ans记录操作次数即为1的个数
             count += 1; 
        }
        return count;
    }
};

总结

n & (-n): 获取n对应二进制最右边的1
n -= n & (-n):将最右边的1变为0
n & (n - 1):将最右边的1变为0