在二进制中寻找1的个数（C++版）

刷题平台

牛客网

题目描述

输入一个整数，输出该数二进制表中1的个数。其中负数用补码表示。

解题思路

由整数转换为二进制数后，可知任何一个非零整数，转换为二进制后至少含有一个 1.

将转换后的二进制中最右边的 1 元素，进行完二进制数减 1 后变为 0 ，后面的 0 全部变为 1 ，之前的元素不变. 将减 1 后的二进制数与原二进制数进行与操作，的到的结果就是将最右边的 1 去掉后的二进制数。每进行一次这样的操作，就相当于二进制中有一个 1 .

例如：转换后的二进制数为 10010. 将最右边的 1 减去后变成 10001，10001&10010 = 10000，可知每完成一次这样的操作，二进制中便有一个元素 1 .

代码

class Solution
{
public:
    int NumberOf1(int n)
    {
        int count = 0;
        while (n)
        {
            count += 1; // 也可以是++count，count++,
            n = (n-1) & n;
        }
        return count;
    }
};

补码：

正数的补码是其二进制表示，即与源码相同。

负数的补码是将其原码的所有位取反，然后加 1 .

O的补码是唯一的，即为 0 .

---

参考博文链接：https://cuijiahua.com/blog/2017/11/basis_11.html