在数组中查找缺失值时无法理解“XOR”背后的逻辑

Question

这是我从这里获得的代码示例。

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获得数组缺失元素的值。

Answer 1

XOR 是按位的。这意味着，给定的两个整数值a, b，a ^ b具有1在该位置位当且仅当要么的位置a或b 是1，但不是两者。

值 15 将按位表示（为简单起见，此处为 8 位）表示为00001111，而值 60 将按位表示为00111100。请注意，15 ^ 60将等于00110011，因为第 2-3 位1仅对 15 位相等，而第 6-7 位0仅对 60位相等。

对于您关于查找数组的缺失元素的问题，它仅在数组包含整数 1 到ARRAY.length0（前提条件）除外的情况下才有效。

• 请注意，XOR 是可交换的和关联的。这意味着a ^ b == b ^ a， 和(a ^ b) ^ c == a ^ (b ^ c) == a ^ b ^ c)
• 对于所有a, b, c。此外，如果对同一个数字进行两次异或运算，它会相互抵消，结果变为 0。给定任何数字n, n ^ n == 0, 也a ^ n ^ n == a。
• 总而言之a，a ^ 0 == a因为如果这个位a是1，那么在那个位置正好有一个位是1。

基于 XOR 的解决方案背后的逻辑是，对于包含在该数组中的所有数字，您对同一数字执行了两次 XOR，这会抵消。唯一的例外是缺少的数字n，因为 0 ^n等于n。

假设ARRAY是一个满足前提条件的数组：

• 情况 1：数字m出现在数组中。执行该 XOR 的条件 (*) 是当循环位于第ith 位置ARRAY[i] == m或m - 1第 th 位置时。我们XOR ^ m在第一次满足条件时有。随着循环的进行，再次满足相同的条件，所以我们有XOR ^ m ^ k ^ m == XOR ^ (m ^ m) ^ k == XOR ^ k，其中k是对条件成立的第一个和第二个索引之间的数字进行异或的结果。

• 情况 2：n数组中缺少数字。请注意，当您遍历循环时，前一个条件 (*) 仅满足一次。我们因此有XOR ^ n.

• 因为 XOR 是可交换和结合的，所以我们最终得到的最终结果为XOR == a^a^b^b^...^n...^x^x^y^y。请注意，除了n循环完成两次异或之外的所有数字，我们都有(a^a)^(b^b)^...^n^(x^x)^(y^y) == 0^0^...^n^...0^0，因此我们获得n了所需的结果。