二进制中1的个数
一、问题描述
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
二、代码与解释
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
};
这是最最简单的一种方法。
如果一个整数为0,那么直接返回0即可。若整数不为0,那么至少有一位为1。
当前有一种操作,可以把这个整数中的1逐一消去,直到没有1为止。这个操作就是:将这个整数减1,再与原来的整数进行与操作,得到的就是将最后一位1消去变为0的过程。
这个操作的原理是:减1操作,会把从右到左数起的第一个1变为0,在这个1的右侧的0(如果有)全部变为1,前面的值保持不变,变的只是这个1以及后面的0。与原来的整数进行与运算,改变了的位全部0。比如100,100减1为011,011&100=000,将从右到左数起的第一个1变成了0,到此为止,操作结束。有多少个1就有多少次这样的操作,直到最后的数变为0停止。