劍指offer11--二進制1的個數

題目描述

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

思路

首先可以利用原碼反碼補碼的知識直接暴力求解。

源碼：首位為符号位，正0負1，後面為真值（絕對值）

反碼：正數等于原碼，負數除了符号位其餘取反

補碼：正數等于原碼，負數為反碼+1

當輸入為正數時，直接除2取餘法；

當輸入為負數時，根據補碼和源碼的關系來轉化成正數。

例如：對于一個8位數，符号位占1位，

補碼	1000 0001	-1	1000 1001	-9
反碼	1000 0000	1000 1000
原碼	1111 1111	-127	1111 0111	-119

補碼與原碼絕對值相加得到128，即2^7。是以輸入一個負數，用128相加得到一個正數，例如-119+128=9，1共有2個，再加上符号位一共是3位。

同理，對于一個32位數，除去符号位，還有31個有效位數，即用2^31去與負數相加。

實作

class Solution {
public:
     int  NumberOf1(int n) {
         if (n==0) return 0;
         int ret=0;
         if (n>0)
         {
             int m=0;
             while (n!=0)
             {
                 m=n%2;
                 n/=2;
                 if (m!=0) ret++;
             }
         }
         else
         {
             ret=NumberOf1(2147483648+n)+1;//2^31相加，最後結果+1（符号位）
         }
         return ret;
     }
};
           

技巧

對于一個不為0的2進制數，肯定存在若幹個1；當對其減1的時候，最右邊的1變成0，這個1右邊的0全變成1，相當于消掉了原來位置上的1，但是又引入了更多的1，那麼如何解決這個引入的問題？隻需要跟原來的數做與運算，例如：

1100-1=

1011 再與

1000 這樣就消去了最右邊的1

如此循環減1下去，直到為0

循環次數即等于1的個數

實作：

class Solution {
public:
     int  NumberOf1(int n) {
         if (n==0) return 0;
         int ret=0;
         while (n!=0)
         {
             ret++;
             n=n&(n-1);
         }
         return ret;
     }
           

知識點

原碼反碼補碼