劍指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;
     }
};