剑指offer - 二进制中1的个数

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8

题意

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

题解

先来看这个
8 —> 1000
7 —> 0111
12 —> 1100
11 —> 1011
可以发现，n-1的二进制表示中，是将n中的最后一个1后面的所有位取反，这与二进制计算是想吻合的。
然后我们可以利用这一性质，依次将n中的1找出来，怎么找呢？
取反之后与原式相与，然后原来的1以及后面的0就全变为0了。
这样我们就可以统计出共有多少个1了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
     int  NumberOf1(int n) {
        int ans=0;
        while(n){
            n&=(n-1);
            ans++;
        }
        return ans;
     }
};