题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
class Solution {
public:
int NumberOf1(int n) {
}
};
补码:
求负整数的补码，将其原码除符号位外的所有位取反（0变1，1变0，符号位为1不变）后加1
原码、反码、补码
- 正数的原码、反码、补码相同
- 负数的反码为除去符号位的其他位取反
- 负数的补码为【反码+1】
- 负数下边界补码为【100……】,无原码与补码(补算出来为【000……】)
- 计算时用补码相加,然后求原码
https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
我自己的方法，没有直接把数想象成二进制。通过正数取余，负数绝对值取余的方法。发现负数补码中除去符号位后0的个数【-5 补码1…1011中的个数为1】即为（其相反数【5】的1的个数【2个1】减1【2 - 1 = 1】），除去符号位共31位,31 - 1 = 30个1
另外,负的边界值另外计算,在本题中是 -2^31 (-2147483648) 补码只有一个1
以下是代码
class Solution {
public:
int NumberOf1(int n) {
int num = 0;
if(n >= 0){
while(n){
num += n % 2;
n = n / 2;
}
}
else if(n == -2147483648)
return 1;
else{
num = 32;
n = ~n;
while(n){
num -= (n % 2);
n = n / 2;
}
}
return num;
}
};
除了解析过程像我这样算之外,因为本身计算机中都是按照二进制的位进行计算的(在负数上按补码运算),所以根本不需要那么麻烦
- 使用1左移与n(0......01)就可以,与的结果是1说明原位是1,cnt ++即可
class Solution {
public:
int NumberOf1(int n) {
int flag = 1,cnt = 0, num = 32;
while(num--){
if((n & flag) != 0){
cnt++;
}
flag = flag << 1;
}
return cnt;
}
};
flag需要移位31次,因为先比较与(&)再移位,移的位要在下一个循环中再进行,使用num应该为32;
再改进
https://www.nowcoder.com/profile/9536154/codeBookDetail?submissionId=17465787
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while (n != 0) {
++count;
n = (n - 1) & n;
}
return count;
}
};
其中
-2^31 = -2147483648
-2^31 - 1 = 100……0 - 1 = 011……1 = 2147483647
100^0& 01……1 = 0
