在数组中查找缺失值时无法理解"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 仅等于 15 的1，而位 6-7 仅等于 60 的0。

对于您关于查找数组缺失元素的问题，仅当数组包含整数 1 到ARRAY.length时，它才有效，除了一个整数为 0(前提条件(。

• 请注意，异或是可交换的和关联的。这意味着，a ^ b == b ^ a和(a ^ b) ^ c == a ^ (b ^ c) == a ^ b ^ c)
• 对于所有a, b, c.此外，如果您两次对同一数字进行 XOR 运算，它将取消 输出，结果变为 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 的条件 (*( 是当循环位于第i个位置(例如ARRAY[i] == m(或第m - 1个位置时。我们XOR ^ m第一次满足条件的时间。随着循环的进行，再次满足相同的条件，因此我们有XOR ^ m ^ k ^ m == XOR ^ (m ^ m) ^ k == XOR ^ k，其中k是条件成立的第一个和第二个索引之间的数字进行异或运算的结果。

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

• 因为异或是交换和结合的，我们最终得到XOR == a^a^b^b^...^n...^x^x^y^y的最终结果。请注意，除了n之外的所有数字在循环结束时被XOR化了两次，我们有(a^a)^(b^b)^...^n^(x^x)^(y^y) == 0^0^...^n^...0^0，因此我们根据需要获得了n。