众所周知，异或是一种很常用的二进制位运算符，运算规则就是相同为0不同为1，与同或恰恰相反（相同以1，不同为0）。

理解异或的性质很重要：

  • 0⊕N=N0 \oplus N = N, N⊕N=0N \oplus N = 0
  • 异或运算满足交换律和结合率

将异或运算理解成无进位相加可以很好地理解上面的性质。

例题一

如何不用额外变量交换两个数？（异或运算的经典题了）

代码实现如下：

package com.test;

public class ExclusiveOR {
    public static void main(String[] args) {
        int a = 10;
        int b = 20;
        System.out.println("交换前a为：" + a + " b为：" + b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("交换后a为：" + a + " b为：" + b);
    }
}

例题二

一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数？

思路分析

这道题乍一看可能挺令人疑惑的，不过其实就是对异或性质的应用。相同的数字各自异或，出现了偶数次的结果为0，那出现了基数次的结果就是它本身了。

代码实现如下：

package com.test;

public class ExclusiveOR {
    public static void printOddTimeNum(int[] arr){
        int eorNum = 0;
        for(int i = 0; i < arr.length; i++){
            eorNum ^= arr[i];
        }
        System.out.println("出现了奇数次的数字为：" + eorNum);
    }
    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 1, 1, 0, 3, 5, 2, 3, 3, 3, 5};
        printOddTimeNum(arr);
    }
}

例题三

怎么把一个int类型的数，提取出其二进制形式最右侧的1并打印。（例如十进制的数字26，二进制形式为00011010，提取最右侧的1后打印00000010）

思路分析

其实这题跟异或关系并不大，但是却对我们解后面的题有一定的帮助，而且也并不是什么高深的东西，属于见过就会，没见过就挺难想到的东西。

代码实现如下：

package com.test;

public class ExclusiveOR {
    public static void decToBin(int num){
        for(int i = 7; i >= 0; i--){
            System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        }
    }
    public static void main(String[] args) {
        int a = 26;
        int rightOne = a & (-a);
        decToBin(rightOne);
    }
}

可以看到，只是将这个数和它的相反数做与运算就可以提取出最右侧的1，这是运用了负数的存储特性。例如-26的二进制形式为11100110，和26的二进制形式00011010做与运算结果就是00000010。至于如何打印一个整型的二进制形式，可以参考《01 打印整型的二进制格式》，这里为了看着方便就只打印了8位形式的二进制。

例题四

一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数

思路分析

这题相当于例题三和例题四的结合。不妨设出现了奇数次的两种数为 a 和 b ，非常容易迈出的第一步是：用一个变量 eorNum 与每个数都异或一次结果为 a ^ b 。但是很可能就卡在这一步了。回想一下例题三，对这道题有什么帮助呢？我们尽管试试提取出 eorNum 二进制形式最右侧的1（因为由题意可知 a 不等于 b ，即 a ^ b 不等于0，所以可以这么做），它代表着在这一位上 a 和 b 是不同的，即一个是0一个是1。不只是它们，其他出现了偶数次的数，也都分属这两个阵营，即这一位上有的为0有的为1。到这里，我们已经可以把 a 和 b 分开了，即让每个数和 eorNum 二进制形式最右侧的1的打印形式进行与运算，结果为1的与一个新变量进行异或操作，一套循环下来，这个新变量就是 a 或者 b 了，再让 a ^ b 与新变量异或一次就是另一个数。

代码实现如下：

package com.test;

public class ExclusiveOR {
    public static void printOddTimeNum(int[] arr){
        int eorNum = 0;
        for(int i = 0; i < arr.length; i++){
            eorNum ^= arr[i];
        }
        int rightOne = eorNum & (-eorNum);
        int eorNum_new = 0;
        for(int i = 0; i < arr.length; i++){
            if((arr[i] & rightOne) != 0){
                eorNum_new ^= arr[i];
            }
        }
        System.out.println("这两个数一个为：" + eorNum_new + " 另一个为：" + (eorNum ^ eorNum_new));
    }
    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 1, 1, 0, 3, 5, 2, 3, 3, 3, 5, 6};
        printOddTimeNum(arr);
    }
}

例题五

一个数组中有一种数出现了KK次，其他数都出现了MM次，其中 1≤K<M1 \leq K < M。怎么找到出现了KK次的数并打印。要求，额外空间复杂度O(1)O(1)，时间复杂度O(N)O(N)。

思路分析

这题相当于前几题的推广，但是实现方法并不算复杂。一个整型在底层以32位二进制的形式存储，不妨开辟一个32位的数组，将二进制形式的每一位加到相应的位上，这时候只要将最终数组的每一位模MM，如果结果为0则说明出现KK次的数在这一位为0，反之则为1。这样就可以将出现了KK次的数还原出来。

代码实现如下：

package com.test;

public class KM {
    public static int KM(int[] arr, int k, int m){
        int[] help = new int[32];
        for(int num: arr){
            for(int i = 0; i < 32; i++){
                help[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for(int i = 0; i < 32; i++){
            help[i] %= m;
            if(help[i] != 0){
                ans |= (1 << i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, -1, -1, 3, 4, -1, 3};
        int k = 2;
        int m = 3;
        System.out.println(KM(arr, k, m));
    }
}

这道题其实可以用哈希表来写对数器，不过这里为了方便就没有提供，有需要的可以自己实现。