二进制运算中，异或无处不在。由于其各种不错的性质在计算机中应用很广。由于日常中很少接触到需要应用到异或的算法，对异或的印象也只停留在各种计算机底层设计中，终归是纸上谈兵。最近接触到了一个使用异或的巧妙算法，便发现自己对异或的理解过于肤浅。

异或简介

  • 交换律
  • 结合律
  • $x;XOR;0 = x$ | $x;XOR;x = 0$
  • $A;XOR;\underline{B;XOR;B} = A;XOR;\underline{0} = A $

使用异或的如上性质，在交换两个变量的值时，可以直接通过异或实现而不用使用额外空间：

A = A ^ B;
B = B ^ A;//B = B ^ A ^ B = B ^ B ^ A = A
A = A ^ B;//A = A ^ B ^ A = B

引子

**问题：**在一个数组中，如果只有一个数重复出现了奇数次而其余数出现了偶数次，设计一个算法来找出这个出现奇数次的数。要求算法满足时间复杂度$O(n)$，空间复杂度$O(1)$。

传统解法

按照传统的思路来的话，可以使用一个HashSet，每次读入一个数据，如果在HashSet中则去掉这个数，反之则将该数字加入HashSet。而这个问题要求$O(1)$的空间复杂度，只能另辟蹊径。

异或解法

可以注意到，这个问题如果使用异或的思想来解决的话便很方便。

假设原数组 nums = {1, 2, 2, 3, 3, 4, 4}所求数字便为 1。初始化 Mask = 0，对每个元素都进行运算Mask ^= num[i]。运算后得Mask = 1。即得到了所求的数字。

应用

**问题：**一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是$O(n)$，空间复杂度是$O(1)$。

传统解法

使用HashSet来实现：

class Solution {
    public int[] singleNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n))
                set.remove(n);
            else
                set.add(n);
        }
        int index = 0;
        int[] res = new int[set.size()];
        for(int i : set){
            res[index++] = i;
        }   
        return res;
    }
}

异或解法

思路：首先利用异或的性质，将数组内所有元素连续异或一次，得到两个只出现一次的元素的异或值。如：nums = {1, 2, 3, 3, 4, 5, 5}连续异或后得到1 ^ 2的值。接下来需要利用异或后的值来分离二者，注意到可以通过二者异或得到的掩码二进制最低位的 1 来分成两组，将问题转换为了引子中所提到的问题，再分别对每组进行连续异或便得到了所求的两个元素。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int mask = 0;
        //得到掩码
        for(int num : nums){
            mask ^= num;
        }
        //得到分组的依据：掩码二进制最右边的 1
        int flag = (-mask) & mask;
        int elem1 = 0;
        int elem2 = 0;
        //分成两个组进行异或，每组异或后的结果就是不相同两个数的其中之一
        for(int num : nums){
            if((flag & num) == 0){
                elem1 ^= num;
            }
            else{
                elem2 ^= num;
            }
        }
        return new int[]{elem1, elem2};
    }
}

最后

利用异或可以实现很多精妙的算法，但是其还是有局限性，且写出的代码往往难以理解，可读性较差，如果代码文档或注释不完整的话很容易让其他人感到迷惑，在日常开发中还是HashSet来的实在。个人认为，一个算法的好坏不应只关注其性能如何如何快，还应注意其可读性如何，以及是否方便维护、线程是否安全等其他方面。