11.二進制中1的個數(java)

題目描述

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

解題思路

位操作方法：

使用一個flag從1開始，每次左移一位，與n進行與操作，不為0時說明這一位為1。

public class Solution {
    public int NumberOf1(int n) {
        int sum = 0;
        int flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) {
                sum++;
            }
            flag=flag << 1;  //左移執行32次後歸0
        }
        return sum;
    }
}
           

改進位操作：

如果一個整數不為0，那麼這個整數至少有一位是1。如果我們把這個整數減1，那麼原來處在整數最右邊的1就會變為0，原來在1後面的所有的0都會變成1(如果最右邊的1後面還有0的話)。其餘所有位将不會受到影響。

舉個例子：一個二進制數1100，從右邊數起第三位是處于最右邊的一個1。減去1後，第三位變成0，它後面的兩位0變成了1，而前面的1保持不變，是以得到的結果是1011.我們發現減1的結果是把最右邊的一個1開始的所有位都取反了。這個時候如果我們再把原來的整數和減去1之後的結果做與運算，從原來整數最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000.也就是說，把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0.那麼一個整數的二進制有多少個1，就可以進行多少次這樣的操作。

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

自己出現的問題

1、<<（左移），>>（右移）皆屬于位運算符.其運算比乘除快，是以我們可以用其優化代碼。

2、<<表示左移，不分正負數，低位補0；

3、>>表示右移，如果該數為正，則高位補0，若為負數，則高位補1；

4、>>>表示無符号右移，也叫邏輯右移，即若該數為正，則高位補0，而若該數為負數，則右移後高位同樣補0