异或如何给出两个数组中不同的数字‽

Question

描述是：&ldquo;给定一个从 1 到 N 的有序数字序列。可能其中一个数字被删除，然后剩余的数字混合在一起。找到被删除的数字。例子：The starting array sequence is [1,2,3,4,5,6,7,8,9]The mixed array with one deleted number is [3,2,4,6,7,8,1,9]Your function should return the int 5.如果没有从数组中删除数字并且与它没有区别，则您的函数应该返回 int 0。请注意，N 可以是 1 或更小（在后一种情况下，第一个数组将为 []）。&rdquo;我写了一个简单的答案：import java.util.*;  public class Kata {    public static int findDeletedNumber (int[] arr, int[] mixedArr) {        Arrays.sort(mixedArr);      for(int i = 0; i < arr.length; i++){        try{          if(arr[i] != mixedArr[i]){            return arr[i];          }        }catch(ArrayIndexOutOfBoundsException e) {          return arr[i];        }      }      return 0;    }}我正在阅读其他人的答案，发现一个我觉得很难深入理解的答案：import java.util.Arrays;public class Kata {    public static int findDeletedNumber(int[] arr, int[] mixedArr) {        return Arrays.stream(arr).reduce((a, b) -> a ^ b).orElse(0) ^ Arrays.stream(mixedArr).reduce((a, b) -> a ^ b).orElse(0);    }}我想得到一些帮助，如果有人关心并有耐心写下解释和/或跟踪，将会有所帮助。目前我可以看到答案，但我不明白。🤯

Answer 1

XOR（异或）真值表

X   Y    result

0   0    0

0   1    1

1   0    1

1   1    0

什么意思X^Y？让我们看一个例子，5^6

dec       bin

5     =  101

6     =  110

------------------ xor

3     =  011

对两个数字进行异或只是将两个数字转换为二进制并应用真值表中的规则。

观察上表，不难看出 X^X = 0 for any integer X

5     =  101

5     =  101

------------------ xor

0     =  000

和X^0 = X

5     =  101

0     =  000

------------------ xor

5     =  101

给定两个数组，对两个数组中的每个元素进行异或，结果意味着类似

(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9) ^ (3 ^ 2 ^ 4 ^ 6 ^ 7 ^ 8 ^ 1 ^ 9)

因为X^Y = Y^X你X^Y^Z = (X^Y)^Z = X^(Y^Z)可以将上面的内容重新排列为

(1 ^ 1) ^ ( 2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4)  ^ (5) ^ (6 ^ 6) ^ (7 ^ 7) ^ (8 ^ 8) ^ (9 ^ 9) 

除了缺少的数字（即 5）之外，一切都相互抵消。