AcWing 26 二進制中1的個數

題目描述：

輸入一個32位整數，輸出該數二進制表示中1的個數。

注意：

• 負數在計算機中用其絕對值的補碼來表示。

樣例1

輸入：9
輸出：2
解釋：9的二進制表示是1001，一共有2個1。
           

樣例2

輸入：-2
輸出：31
解釋：-2在計算機裡會被表示成11111111111111111111111111111110，
      一共有31個1。
           

分析：

方法一：

對負數單獨處理，我們知道，負數的補碼等于其原碼各位取反加1，或者說，是其原碼最後一個1之前所有的數都反轉過來，比如-2的補碼，是由-2的原碼除了後兩位及符号位不變，其它位均取反得到，也可以是2的原碼除了後兩位前面所有位取反得到。

這意味着求負數的補碼，我們隻需要找到其相反數的原碼最後一個1的位置即可，容易想到樹狀數組裡的lowbit運算，也就是n&（-n），設x的二進制表示中有ans個1，且其最後一個1在第p位（自右向左），則-x中1的位數為32-p-（ans-1）+1=34-p-ans。（仔細思考可了解，這裡不再贅述）。是以我們隻要對負數情況先做個标記求出p，然後對n取相反數，之後按照正數一樣的求，最後根據标記再來判斷最終結果即可。

需要注意的是對應10000...（31個0），表示的是-2147483648，也就是32位整數補碼中比原碼多表示的那個數。如果我們對其取相反數，得到的數會超過32位，引起錯誤，是以單獨判斷一下即可。代碼如下：

class Solution {
public:
    int NumberOf1(int n) {
        int ans = 0,p = 0;
        bool flag = false;
        if(n < 0){
            if(n == -2147483648) return 1;
            flag = true;
            int k = n & (-1)*n;
            while(k > 0){
                k >>= 1;
                p++;
            }
            n = (-1) * n;
        }
        while(n > 0){
            if(n & 1)   ans++;
            n >>= 1;
        }
        if(flag)    ans = 34 - p - ans;
        return ans;
    }
};
           

方法二：

如果說方法一是讓我們加深對原碼補碼的了解，那麼方法二就是利用了強制類型轉換。在計算機組成原理中資料表示與運算一章，我們可以看見：強制類型轉換并不改變變量的存儲内容，而隻是改變其解釋方式。

回到問題起點，我們為什麼要單獨對負數單獨處理，那是因為計算1個數的循環裡，判斷條件是n大于0，是否可以将判斷條件改為n不等于0，以此來對正數負數統一判斷？對于正數肯定是可以的，對于負數想象着每次右移也更加接近0了，其實不然，這樣對負數每次右移一位，左端會補符号位，也就是一直向右移，符号位始終是1，進而造成死循環。

為了避免死循環，我們可以将n強轉為無符号類型，這樣一來，右移時左邊隻會補0，便可以統一處理了。

class Solution {
public:
    int NumberOf1(int n) {
        int ans = 0;
        unsigned int un = n;
        while(un > 0){
            if(un & 1)   ans++;
            un >>= 1;
        }
        return ans;
    }
};