异或相当于不进位相加

异或的性质

• 0^N = N

• N^N = 0

• A^B = B ^ A交换律

• (A^B)^C = A^(B^C)结合率

• A^B^C^D^E 与异或的顺序无关

不用额外变量交换两个数

A = A ^ B
B = A ^ B
A = A ^ B

设A = 甲，B = 乙

第一步：A = A ^ B = 甲 ^ 乙

第二步：B = A ^ B = 甲 ^ 乙 ^ 乙 = 甲 ^ (乙 ^ 乙) = 甲 ^ 0 = 甲 = A

第三步：A = A ^ B = 甲 ^ 乙 ^ 甲 = （甲 ^ 甲）^ 乙 = 0 ^ 乙 = 乙 = B

需要注意的是，使用此方法的前提是不是同一空间的数，比如数组中

如果 a = b = 1;

用上述方法交换arr[a]和arr[b]就会发现arr[a]会被刷新为0，因为第一步就是同一个数在进行异或，这与两个相同的数交换不同

/*
int a = b = 1;
a = a ^ b = 1 ^ 1 = 0;
b = a ^ b = 0 ^ 1 = 1;
a = a ^ b = 0 ^ 1 = 1;
int[] arr = {1,1};
arr[a] = arr[a] ^ arr[b] = arr[1] ^ arr[1] = 1 ^ 1 = 0;
arr[b] = arr[a] ^ arr[b] = arr[1] ^ arr[1] = 0 ^ 0 = 0;//arr[1]的数已经完全变为了0
arr[a] = arr[a] ^ arr[b] = arr[1] ^ arr[1] = 0 ^ 0 = 0;
*/

异或的妙用

有这样一道题

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

传统做法可以创建一个哈希表，去做一个词频统计

但如果用异或运算的性质，就可以省去那个哈希表

public static int main(int[] arr){
    int eor = 0;
    for (int j : arr) {
        eor = eor ^ j;
    }
    return eor;
}

我们知道N ^ N = 0，如果给定的数组符合题目的要求，那么就只有一个数是奇数，最后的eor也就是这个数

那么将题目升级一下

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

将这道题按上一道题那样进行操作之后，最后的eor = a ^ b(a,b就是那两种数，因为a!=b,所以eor一定不为0)

那么eor二进制形式下的最右侧的那个1，就可以将a和b分为两个范围，假设eor最右侧的1是第三位上，

整个数组一类是第三位是1，还有一类是第三位为0，a和b一定是以这两类分开来的，因为eor是a ^ b得来的。异或结果为1，只有一个为1，一个为0.

那么既然我们将俩个数分开来了，那么将其中一类进行一次挨个异或操作，就可以将其中的答案之一挑选出来。

那么现在的问题就是如何去从一个int的数（a）取出最右侧的1

这里直接提供方法

ans = a & ( - a )

如何判断一个数是否该位上是否为1，

我们考虑一下与运算，全为1才是1，那么正好可以判断它与完之后是不是0来分类，如果这一位上它是0，那么与完的结果全部为0。

将为0的再进行一次异或运算就可以得出答案之一one，再将eor和one异或一下，就可以将另一个答案得出

    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // a 和 b是两种数
        int rightOne = eor & (-eor); // 提取出最右的1
        int onlyOne = 0; 
        for (int i = 0 ; i < arr.length;i++) {
            if ((arr[i] & rightOne) != 0) {
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }