2. 異或算法

2.1 異或基礎

1. 0^N == N N^N == 0；
2. 記為無進位相加即可，1+1 = 0；
3. 異或運算滿足交換律和結合。

2.1.1 不用額外變量交換兩個數

解法：a^ba = b，a^bb = a。

2.1.2 找出現奇數次的數

1. 題目

? 一個數組中有一種數出現了奇數次，其他數都出現了偶數次，怎么找到并打印這種數。

2. 思路

? 數組里每個元素都異或，兩兩相消，就只剩下奇數次的那個數

3. 代碼

public static void main(String[] args) {
    int[] arr = {1,3,4,1,3,4,1,3,4,5,1,3,4};
    int ans = 0;
    for (int i = 0; i < arr.length; i++) {
        ans ^= arr[i];
    }
    System.out.println(ans);
}

2.2 提取右側(最低位)的1

1. 題目

? 怎么把一個int類型的數，提取出最右側(最低位)的1來

2. 思路

1. 取反加一再和原來相與 a&(~a+1)

? 取反：這樣每一位都不一樣，之前的0位置都變成了1，假設此時的值為b。

? 加一：這樣在右面+1就可以讓他一直進位直到第一個0（也就是沒取反的時候的1的位置），假設此時值為c。

? 相與：此時c的狀態是最低的1往右的值都是0，最低一位的1的位置和a相同，這一位再往右每一個都是不一樣的，所以相與之后，直接就可以得到結果。

注意: ~a+1 就等于-a，所以也可以寫成a&(-a)

2. 直接暴力

? 先找位置，然后再把1右移

3. 代碼

取反加一：

System.out.println((a&(~a+1)));
System.out.println((a&(-a)));

暴力：

private static int findRightest(int a) {
    int rightPos = 0;
    // 找最低位的1
    for(int i = 0; i < 32; i++){
        if((a & 1) == 1){
            rightPos = i;
            break;
        }
        a = a>>1;
    }

    a = 1;
    // 右移
    for (int i = 0; i < rightPos; i++) {
        a = a << 1;
    }
    System.out.println(a);
    return a;
}

2.3 找到兩種奇數數

1. 題目

一個數組中有兩種數出現了奇數次，其他數都出現了偶數次，怎么找到并打印這兩種數

2. 思路

? 全部異或，只留下eor = a^b

? 因為a != b，所以二進制的ab至少有一位不一樣，即eor != 0，也就是至少存在一位為1。

? 既然有一位為1，代表a，b在這一位不同（異或：同0異1），那么就可以通過這一位來區分數組。

? 這一位為0的放一邊，為1的放一邊，分別異或，這樣得到的數就可以區分出來ab了。

只要是eor有一位為1就可以區分，具體是哪個無所謂，所以不妨設是最右側的一個。

3. 代碼

private static int[] getAB(int[] arr) {
    // 先異或，得到eor=a^b;
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    // 對于ab，最右側一位的1提取出來
//        System.out.println(eor);
    int rightest = eor&(-eor);
//        System.out.println(rightest);
    // 根據這一位來區分屬于誰
    // 不妨設a在這位為0，b在這位為1
    int[] ans = new int[2];
    for (int i = 0; i < arr.length; i++) {
        if((arr[i] & rightest) == 0){
            ans[0] ^= arr[i];
        }else{
            ans[1] ^= arr[i];
        }
    }
    return ans;
}

2.4 找到出現k次的數

1. 題目

? 一個數組中有一種數出現K次，其他數都出現了M次，M > 1, K < M，

? 要求：找到出現了K次的數，額外空間復雜度O(1)，時間復雜度O(N)

2. 思路

? 利用長度為32的數組，記錄下每一位置出現1的次數，模M除K就得到二進制的所求數，再轉為十進制。

3. 代碼

private static int findKTimes(int[] arr, int m, int k) {
    int[] times = new int[32];
    // 記錄所有數的32位的出現的次數
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < times.length; j++) {
            if((arr[i]&(1<<j)) != 0){
                times[j] ++;
            }
        }
    }
//        Arrays.stream(times).forEach(System.out::println);
    // 所有數%m/k 得到的數組合成int
    int ans = 0;
    for (int i = 0; i < times.length; i++) {
        times[i] = times[i]%m/k;
    }

    // 組合成int
    for (int i = 0; i < times.length; i++) {
        // cur = 1 1 0 1
        // times = 1 0 1 1
        ans += (times[i]<<i);
    }
    return ans;
}

總結

以上是生活随笔為你收集整理的02-异或算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。