JZ11_二進制中1的個數

知識點：補碼、位運算

題目連結

題目描述

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

示例1

輸入: 10

傳回值: 2

解題思路

1. 我們需要注意的是 整數包括負數 負數在計算機中是以補碼的形式存儲的
2. 正數的正碼、反碼和補碼都相同
3. 負數的補碼 = 負數的反碼 +1
4. 8位的二進制 表示-1 是 1111 1111 因為 1的反碼為1111 1110 再加一 是1111 1111
5. 注意左移，存在循環左移，負數往右移前面添1
6. 是以這道題可以用一個正的0x01 不斷左移比較
7. 還有一種巧妙的解法，和比目前數減1的與一下。二進制數：val :1101000, val-1: 1100111 那麼val & （val-1） : 1100000

代碼

#include "cheader.h"
class Solution {
public:
    /*
    錯誤代碼：
    當n是負數的時候，如-1的時候 右移 最高位會補1
    int  NumberOf1(int n) {
        int ans = 0;
        while (n != 0) {
            if (n & 1)
                ++ans;
            n >>= 1;
        }
        return ans;
    }*/
    //讓一個數0x01從右向左與val的每一位進行&操作來判斷
    int NumberOf1(int n) {
        int ans = 0;
        int mark = 0x01;
        while(mark != 0){
            if(mark & n)
                ans++;
            mark <<= 1;
        }
        return ans;
    }
    /*
    可以對從右向左的第一位1直接判斷，遇到0直接略過
    現考慮二進制數：val :1101000, val-1: 1100111 那麼val & （val-1） : 1100000
     */
    int NumberOf1_2(int n) {
        int ans = 0;
        while(n != 0){
            ans ++;
            n = n & (n-1);
        }
        return ans;
    }
};
int main()
{
    Solution s;
    cout<<s.NumberOf1(-1)<<endl;
    return 0;
}


           

今天也是愛zz的一天！