java - xor如何在两个数组中给出不同的数字‽

Question

我已经回答了以下问题:Lost number in number sequence .描述是:

“给定一个从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 或更小(在后一种情况下，第一个数组将为 [])。”

我写了一个简单的答案:

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);
    }
}

答案链接:https://www.codewars.com/kata/reviews/595be553429e11365c00006f/groups/59bef3a1eda42eb0bc001612

我想得到一些帮助，如果有人关心并有耐心写下解释和/或跟踪，将会有所帮助。目前我可以看到答案，但我不明白。 🤯

此外，我试图通过阅读来理解它: What does the ^ operator do in Java? https://www.geeksforgeeks.org/bitwise-operators-in-java/

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 对于任何整数 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，其他一切都相互抵消。