剑指Offer11 二进制中1的个数

题意

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

思路

做这个题目时，发现自己对计算机中补码反码原码的理解不够深入，这里再复习一下：

在计算机中，所有的数值都是以其补码表示的，因为用补码可以将两个数的剑法转化为加法，方便加法器工作。

对于正数，其源码、补码、反码都是一致的（除此之外还有移码，就是将补码的符号位取反），一般以最高位作为符号位，正数的符号位为0，负数为1，则例如32位（4字节）的有符号整型数，第一位是符号位，低位的31位是数值位，以补码表示的话，最大的正整数为（2^31 - 1)，即符号位为0，其余为1（0111…1111)

对于负数，符号位为1，其反码为原码除符号位外全部取反， 补码为反码+1，则表示-(2^31 - 1)的补码应为（111…1111）,但实际上还可以再减1，即将（1000…0000)表示-231。所以32位最小整数位-231。

对于0，有正0负0：

[+0]原码=0000 0000， [-0]原码=1000 0000

[+0]反码=0000 0000， [-0]反码=1111 1111

[+0]补码=0000 0000， [-0]补码=0000 0000

会发现其实0只有一种补码，那是因为补码加1进位将符号位舍弃，溢出后直接取0000 0000，这也是为了保证加法器可以算减法。

还有一个知识：负数的补码等于其相反数的补码减一再逐位取反，例如四位表示的7，其补码位0111，则-7的补码位1001，验证：将两个数的补码相加（0111）+（1001） = （0000）最高位溢出得到结果0，符合运算规则。

回到题目，则可以知道，若输入的数据是整数，则可以直接不断右移，判断最后一位是否为1，其实就是看对2取模是否为1，若输入的是负数，则先对其取反再减一，则得到的这个正数其实将其所有位取反就得到原来负数的补码，可以先计算这个正数的1的个数，再用总位数减去该值，就是负数补码中1的个数。

代码

class Solution {
public:
     int  NumberOf1(int n) {
         bool flag = false;
         if(n < 0){
             flag = true;
             n = -n - 1;   //把负数转换为相反数减一，因为负数的补码等于相反数原码减一，再将所有位取反
         }
         int count = 0;
         while(n){
             if(n % 2)
                 count++;  //计算正数的1
             n /= 2;
         }
         if(flag)
             count = 32 - count;   //若n原来是负数，则其补码中的1恰好和转换后的正数的1互补
         return count;
     }
};