題目描述

輸入一個整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個數(shù)。其中負(fù)數(shù)用補碼表示。

時間限制：1秒 空間限制：32768K

代碼實現(xiàn)

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

解題思路

我們先來看一個數(shù)的二進(jìn)制，就比如 12 的二進(jìn)制表示是 1100 ，如果一個整數(shù)不等于 0 的話，那么至少有一位是 1。如果我們把這個整數(shù)減 1 ，也就是 11 的二進(jìn)制是 1011，我們發(fā)現(xiàn)原來整數(shù)的最右邊的 1 就會變成 0 ，而原來 1 后邊的所有 0 都會變成 1 （如果原來 1 后邊有 0 的話），原來 1 前邊的將不變。

也就是說把一個整數(shù)減 1 之后，得到的結(jié)果就是把原來整數(shù)從最右邊的 1 開始的所有位都做了取反操作，然后再把原來的整數(shù)和減 1 之后的數(shù)做與運算，即從原來數(shù)的最右邊的 1 開始所有位都變成了 0 。比如： 1100&1011=1000，也就是說把一個數(shù)減 1 再與原來的數(shù)做與運算，就是把原來數(shù)的最右邊的 1 變成了 0，那么我們可以對一個二進(jìn)制的整數(shù)進(jìn)行多少次這樣的運算，就表示這個整數(shù)的二進(jìn)制中有多少個 1 。

延伸問題

• 與運算（&）

  運算規(guī)則：1&0=0；0&1=0；0&0=0；1&1=1。

  兩位同時為 1 ，結(jié)果才為 1，否則為 0。

• 或運算（|）

  運算規(guī)則：1|0=1；0|1=1；0|0=0；1|1=1。

  只要有一個為 1 ，那么結(jié)果就為 1。

• 異或運算（^）

  運算規(guī)則：1^0=1；0^1=1；0^0=0；1^1=0；

  如果兩個相應(yīng)位為“異”（值不同），則該位結(jié)果為 1，否則為 0。

• 取反運算（~）

  運算規(guī)則：~1=0；~0=1；

  對一個二進(jìn)制數(shù)按位取反，即將 0 變 1，1 變 0。

• 左移運算（<<）

  將一個運算對象的各二進(jìn)制位全部左移若干位（左邊的二進(jìn)制位丟棄，右邊補0）。

  例如：a=a<<2，將 a 的二進(jìn)制位左移兩位，右邊補 0。

  若左移時舍棄的高位不包含 1，則每左移一位，相當(dāng)于該數(shù)乘以 2，即 a=a*2。

• 右移運算（>>）

  將一個數(shù)的各二進(jìn)制位全部右移若干位，正數(shù)左補 0，負(fù)數(shù)左補 1，右邊丟棄。

  例如：a = a>> 2，將 a 的二進(jìn)制位右移 2 位。

  每右移一位，相當(dāng)于該數(shù)除以2。