题目描述

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

注意

负数在计算机中用其绝对值的补码来表示。

数据范围

$−100\leq 输入整数 \leq 100$

样例1

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

样例2

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

这道题是一道位运算题，解法有很多种，这里会选$3$个为大家讲解。

NO.1 循环（固定次数）

一个$int$类型的变量有$32$位，想要取出第$i$位就是n >> i & 1，因为$1$的二进制是$000…01$所以和任何数进行&运算结果都只可能是$0$或$1$。

代码：

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        for (int i = 0; i < 32; i ++)
            res += n >> i & 1;//如果n的第i位是1，则res+1；否则什么也不会发生
        return res;
    }
};

NO.2 循环（不固定次数）

在第一种方法的基础上，我们可以用while来做这道题，先看一眼代码：

class Solution {
public:
    int NumberOf1(int n) {
        unsigned int x = n;
        int res = 0;
        while (x) res += x & 1, x >>= 1;
        return res;
    }
};

这边有一个问题是，如果是负数的话，每次右移运算都会在左边补$1$，这会造成循环永远不终止，所以这边可以给它转成无符号整型，这就不会出现问题了。

NO.3 $lowbit$

先说一下$lowbit$是什么东西。

$lowbit(x)$表示$x$的最后一位$1$，比如$10$的二进制表示是$1010$，那$lowbit(x)$就应该是$(10)_2$也就是$2$。

那$lowbit(x)$怎么求呢？

其实很简单，只要返回x&(-x)就行了。可又为什么呢？

是因为$C++$中的负数使用补码表示的，而补码等于反码（就是把$x$的二进制中的每一位都取反）$+1$，所以x&(-x)=x&(~x+1)。

要证明x&(~x+1)的正确性，可以先看下图：

很明显，红色数字左边的原码与补码都是相反的，而红色数字右边的原码与补码都是$0$，所以最后只有红色数字一个$1$，故x&(-x)是成立的。

那么这道题可以让$n$反复减去$lowbit(n)$直到$n$为$0$，减去的次数就是答案。

代码:

class Solution {
public:
    //返回x的lowbit值
    int lowbit(int x)
    {
        return x & (-x);
    }
    int NumberOf1(int n) {
        int res = 0;
        while (n)
        {
            n -= lowbit(n);//每次减去lowbit(n)
            res ++;
        }
        return res;
    }
};

好了，这就是这篇题解的全部内容。如果觉得好的话，不妨给我一个赞吧！如果觉得有问题，也请在评论区指出。
那么，感谢观看！Thanks♪(･ω･)ﾉ！
$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$