【技巧總結】java位運算

位運算可以大幅度提高代碼的運行效率，是每個人都應熟練掌握的解題技巧，首先感謝英雄大佬的b站視頻，感興趣的話可以前往b站一睹為快：可能會占據你陪女朋友的時間，但是你要相信……

位運算兩大類：

邏輯位運算子
位移運算子

邏輯位運算子包括：
邏輯與（&&）：只有兩個運算元都為true是才是true，其他則為false，
邏輯或（||）：如果其中一個或兩個運算元都是true，那么回傳true，如果兩個運算元都是false，那么回傳false，

位移運算子包括：
位與運算子（&）：只有對應的兩個二進位均為1時，結果位才為1 ，否則為0，
位或運算子（|）：只要對應的兩個二進位有一個為1時，結果位就為1，
異或運算子（^）：只有對應的兩個二進制位相同的時候，結果位回傳0，否則回傳1，
按位取反運算子（~）：轉換為二進制數后，0變1，1變0，
左移運算子（<<）:把位按指定的值向左移動對應的位數，超過的位將丟失，空位補0，左移也可以看作是對此數乘以2，
右移運算子（>>）:把位按指定的值向右移動對應的位數，移動程序中，正數最高位補0，負數最高位補1，右移也可以看作是對此數除以2，

舉一些栗子：
1.231. 2 的冪

分析：當這個是小于或者等于0的時候，一定不是2的冪，我們可以知道二進制最高位為 1，其余所有位均為 0，所以這個數如果是2的冪，一定是1加上若干個0，那么我們減去一，也就是0加上若干個1，我們讓這兩個數進行位與運算，那么一定是若干個0，也就是我們有：n & (n - 1) == 0，所以此題可解，

class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && ((n-1) & n)==0;
    }
}

2.342. 4的冪

分析：4的冪一定是2的冪，但是2的冪不一定是4的冪，我們可以推出，2的偶數次冪模3等于1，2的奇數次冪模3等于2，而2的偶數次冪正好是4的冪，所以我們可以知道，如果一個數字是2的冪，并且它模3等于1，那么它一定就是4的冪，

class Solution {
    public boolean isPowerOfFour(int n) {
        return (n > 0) && (n & (n - 1))== 0 && (n % 3 == 1);
    }
}

3.191. 位1的個數

分析：我們把一個數a的二進制數假設為（…1000），那么我們剪去1，就可以得到了（…0111），我們讓（…1000）&（…0111），那么就可以得到（…0000），于是我們這樣就可以把a的二進制數最低位的1消去了，我們通過這種操作，就可以把所有的1都消去了，然后統計消去的1的個數，我們就可以得到結果了，

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int number = 0;//記錄1的個數
        while(n!=0){
            n &= (n - 1);
            ++number;
        }
        return number;
    }
}

4.面試題 16.01. 交換數字

分析：我們先看一個運算規則，規則：0^0=0； 0^1=1； 1^0=1； 1^1=0；所以我們可以得到兩個相同的數進行異或運算，可以得到0，那么一個數和0進行異或運算，就是得到這個數的本身，我們看下面這張圖，這樣就可以將a與b進行交換了：

class Solution {
    public int[] swapNumbers(int[] numbers) {
        numbers[0] = numbers[0]^numbers[1];
        numbers[1] = numbers[0]^numbers[1];
        numbers[0] = numbers[0]^numbers[1];
        return numbers;
    }
}

5.136. 只出現一次的數字

分析：我們先看一個運算規則，規則：0^0=0； 0^1=1； 1^0=1； 1^1=0；所以我們可以得到兩個相同的數進行異或運算，可以得到0，那么一個數和0進行異或運算，就是得到這個數的本身，那么我們只要不斷異或下去，就可以得到把出現兩次的數全部解決，所以就可以剩下只出現了一次的數字，

class Solution {
    public int singleNumber(int[] nums) {
        int number = 0;
        for(int i = 0; i < nums.length; i++){
            number = number^nums[i];
        }
        return number;
    }
}

6.461. 漢明距離

分析：由下圖可知，異或完去求所得結果上1的個數就是所求的漢明距離，

class Solution {
    public int hammingDistance(int x, int y) {
        int n = x^y;
        int number = 0;
        while(n != 0){
            n &= (n - 1);
            number++;
        }
        return number;
    }
}

7.693. 交替位二進制數

分析：我們對這個正整數的二進制進行兩位兩位判斷，從尾部開始，向頭部兩位兩位判斷，如果相鄰的這兩個數是11或者是00，那么就不符合題意，我們又可以知道，二進制的00對應十進制就是0，二進制的11對應十進制就是3，于是我們可以讓3的二進制不斷與這個數的二進制數進行&運算，我們看一張圖：

class Solution {
    public boolean hasAlternatingBits(int n) {
        while(n!=0){
            if( (n & 3)==3 || (n & 3) == 0 ){
                return false;
            }
            n>>=1;
        }
        return true;
    }
}

8.1863. 找出所有子集的異或總和再求和

分析：我們給定一個陣列，將里面的子集進行分解：
如果二進制對應的位置上有1，就證明在集合里面，否則就不在，

上面的意思是，在i這個數的二進制表示中，從低到高第 j 位是否是1，把 1 的數字對應的位都進行異或，得到的結果累加到最終結果就是答案，

class Solution {
    public int subsetXORSum(int[] nums) {
        int answer,sum = 0;
        for(int i = 0; i < (1<<nums.length); i++){
            answer = 0;
            for(int j = 0; j < nums.length; j++){
                if((i&(1<<j))!=0){
                    answer^=nums[j];
                }
            }
            sum = sum + answer;
        }
        return sum;
    }
}

9.371. 兩整數之和

分析：首先我們可以看一下十進制的情況： 9+3=12，
第一步：相加各位的值，但是不算進位，得到2，
第二步：計算進位值，得到10，
第三步：重復上述兩步，得到相加值為12，
￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥
我們可以同理計算二進制值相加： 比如101和111
第一步：相加各位的值，但是不算進位，得到010，二進制的每位相加就相當于各位做異或操作，101^111，
第二步：計算進位值，得到1010，相當于各位進行與操作得到101，再向左移一位得到1010，(101&111)<<1，
第三步：重復上述兩步，各位相加 010^1010=1000，進位值為100=(010 & 1010)<<1，
繼續重復上述兩步：1000^100 = 1100，進位值為0，此時我們跳出回圈，1100為最終結果，當我們的進位為0，即為最終所求結果，

class Solution {
    public int getSum(int a, int b) {
        return b == 0 ? a : getSum(a^b,(a&b) << 1);
    }
}

10.面試題 05.01. 插入

分析：先把N的第i到第j都歸零，然后把M插入到N的對應位置，歸零可以使用位與&運算，將其和第k位為0，其余位為1的二進制數進行運算，達到消零操作：
然后我們在將N左移i位，和現在的數進行位或，就可以得到結果:

class Solution {
    public int insertBits(int N, int M, int i, int j) {
        for(int k = i; k <= j; k++){
            N &= ~((long)1<<k);
        }
        return N|(M<<i);
    }
}

學習位運算最好的時間是在大一，其次就是現在，