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

Question

这是我从here获得的代码示例.

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.length 时，它才有效。除了一个整数为 0(前提条件)。

• 请注意，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，结果相互抵消。唯一的异常(exception)是缺少号码 n ，如 0 ^ n等于 n .

假设ARRAY是满足前提条件的数组:

• 情况1:号码m出现在数组中。执行 XOR 的条件 (*) 是当循环位于 i 时。这样的位置 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根据需要。