剑指 offer 笔记 11 | 二进制中1的个数

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

思路分析
计算出，一个整数二进制形式下 1 的个数有多少，例如 2 ==》0010 那么 2 的二进制 1 个数为 1 个。

这道题花了一个早上去理解，涉及位运算知识点，废话少说，直接上代码，虽然是大神的代码。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
    }
}

其中 n = n & (n - 1); 最为巧妙了， & 是（与运算符）位运算，针对二进制，只要有一个为 0，就为 0

举个例子， 2 ===》 0010； 1 ===》 0001

那么 2&1 ，得出来为 0 ；既是 0010 & 0001 结果为 0000 （二进制结果）；

引用大佬的话 ：一个二进制数 1100，从右边数起第三位是处于最右边的一个 1。减去 1 后，第三位变成 0，它后面的两位 0 变成了 1，而前面的 1 保持不变。因此得到的结果是 1011。

我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减去 1 之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成 0。

如 1100&1011=1000 .也就是说，把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0。那么一个整数的二进制有多少个 1，就可以进行多少次这样的操作。

参考文献：https://www.nowcoder.com/profile/562667/codeBookDetail?submissionId=1520125