无法理解用XOR查找数组中缺失值背后的逻辑

我来给你掰扯清楚这个用XOR找缺失元素的逻辑，核心就是利用了XOR的几个超实用特性！先看你贴的这段代码：

public class Snippet {
    private static final int[] ARRAY = {1, 4, 3, 18, 2, 8, 9, 6, 5, 10, 11, 12, 13, 14, 15, 16, 17, 19, 0, 20};
    //{1,2,4,5,6,8,7,9,3}
    private int getMissingElem() {
        int XOR = 0;
        for (int i = 0; i < 20; i++) {
            if (ARRAY[i] != 0) {
                XOR ^= ARRAY[i];
            }
            XOR ^= (i + 1);
        }
        return XOR;
    }
    public static void main(String[] args) {
        Snippet s = new Snippet();
        System.out.println(s.getMissingElem());
    }
}

先记住XOR的三个核心特性 #

• 任何数和自己做XOR，结果都是0：a ^ a = 0
• 任何数和0做XOR，结果还是它自己：a ^ 0 = a
• XOR满足交换律和结合律，也就是a ^ b ^ c = a ^ c ^ b = (a ^ b) ^ c，运算顺序不影响最终结果

结合代码拆解逻辑 #

你的数组是包含0到20的数，但缺了一个（这里缺的是7）。代码里的循环从i=0到i<20，一共执行20次，每次循环做两件事：

1. 如果数组当前元素不是0，就把它和XOR变量做异或
2. 把i+1（也就是从1到20的所有整数）和XOR变量做异或

我们把所有参与异或的数展开来看：

• 数组里的非0元素：1,4,3,18,2,8,9,6,5,10,11,12,13,14,15,16,17,19,20（缺了7）
• i+1的所有值：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20（1到20全齐）

根据XOR的交换律和结合律，这些数里所有出现过两次的数都会两两抵消成0（比如1^1=0、22=0……6^6=0、88=0……20^20=0），最后就只剩下那个只出现过一次的数——也就是缺失的7！

至于代码里跳过数组中的0，是因为0不在我们要找的1-20范围内，而且0和任何数异或都不会改变结果，所以跳过它完全不影响最终计算。

内容的提问来源于stack exchange，提问作者new user