每日寫題分享--關于位運算

&：對應為有0，則為0，其余為1；

n & (n - 1 ):去掉右邊第一個1，

n & 1 == 1 則說明概述最右位位1，即n為奇數，

|：對應位有1，則是1，其余為0，

^:一樣的位置為0，不一樣的位置為1，

n ^ n = 0;

0 ^ n = n;

按位異或^可以用于10以內的加法（因為不會產生進位），如果產生進位，則需要用到按位與&配合，假如a & b = c，我們知道，只有相同位置都是1才為1，二進制加法為兩個1則進位，所以c中有1的位都是要進位（左移一位）的，可以用&記錄需要進位的數，

所以加減法可以用&和^的配合來完成，看題

題目描述：

題目鏈接

代碼實作如下：

//方法一：回圈
class Solution {

    public int add(int a, int b) {
        while (b != 0) {
            int c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

//方法二：遞回
class Solution {

    public int add(int a, int b) {
        if (b == 0) return a;
        int c = (a & b) << 1;
        a ^= b;
        return add(a,c);
    }
}

再來看這題，求二進制中1的個數，上面說到，n&(n - 1)可以去掉右邊第一個1.可以利用這個特性求解本題，

題目描述：

題目鏈接

代碼實作如下：

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

下面再來看這題，求陣列中數字出現的次數I，

題目描述：

解題思路：

全員進行異或操作即可，考慮異或操作的性質：對于兩個運算元的每一位，相同結果為 0，不同結果為 1，那么在計算程序中，成對出現的數字的所有位會兩兩抵消為 0，最終得到的結果就是那個出現了一次的數字，而本題中出現一次的數有兩個，所以所有數異或的結果就是那兩個只出現一次的數異或的結果，假定為這個結果為res，

那么這一方法如何擴展到找出兩個出現一次的數字呢？

如果我們可以把所有數字分成兩組，使得：

1、兩個只出現一次的數字在不同的組中；

2、相同的數字會被分到相同的組中，

下面進行分組，首先考慮兩個相同的數字一定要分在一組，這個很容易實作，我們只需要固定一個二進制位，只要兩個數字在這一位相同，就肯定劃分在一組，下面就是要將那兩個只出現一次的數字x,y分到兩個組中，兩邊分別異或和，相同的兩兩抵消，最后兩邊的異或和就是x,y，接下來就剩一個問題，如何把x,y分到兩個組里面去，由于res是所有數字異或和，等同于x,y的異或和，x,y不相同，根據異或的性質，res二進制里面的1都是x,y不相同的地方，我們只要找到res中的任意一個1，這里解題我找的是右邊第一位1，這個位置記為div，x,y在位置div上是1，根據異或性質，在這個位置上x,y不一樣，一個為0，一個為1，然后在遍歷陣列依次將陣列元素與div按位與&運算，那么x,y在&div是，肯定有一個為0，另一個非0，這樣兩個數就會被分到兩個組中，然后分別求異或和就是答案，

代碼實作如下：

class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;     //兩個不同值的異或結果,假設為x,y
        }

        int div= 1;
        while ((div & res) == 0) {  //res里的所有1都是代表x，y不相同的位
            div <<= 1;       //找到res從右數的第一個1（x,y的不相等的位）
        }

        int a = 0,b = 0;        //分組
        for (int num : nums) {
            if ((div & num) == 0) {     //能把x，y分開，因為x，y得到的結果肯定是不同的，仔細理解，有點像負負得正，其次陣列其他相同的數字也會被分到相同的組，因為相同的數字得到的結果相同，
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a,b};
    }
}

再來練習最后一道關于位運算的題，陣列中數字出現次數II

題目描述：

這題比上一題其實簡單一些，沒有那么難理解，只要有思路就好做，首先題目說除了一個數字target外，其他的數字都出現三次，意味著沒有target的情況下，各二進制位出現的次數都是3的倍數，統計所有數字的各二進制位中 1的出現次數，并對 3 求余，結果則為只出現一次的數字，

代碼實作如下：

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];     //統計個數
        for (int i = 0;i < nums.length;i++) {
            for (int j = 0;j < 32;j++) {
                counts[j] += (nums[i] >> j & 1) == 1 ? 1 : 0;   //將每個數字右移j位再&1，判斷最后一位是不是1，然后加到對應位的counts中，
            }
        }
        int target = 0;        
        for (int i = 31;i >= 0;i--) {       
            target <<= 1;      //從后向前將結果輸出，每個位置對應counts中的數字后左移判斷下一個位置
            if ((counts[i] % 3) == 1) { //說明target在該位置上是1
                target |= 1;   
            }
        }
        return target;
    }
}