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.

如果没有数字从数组中删除并且与它没有区别，你的函数应该return 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);
    }
}

对link的回答：https://www.codewars.com/kata/reviews/595be553429e11365c00006f/groups/59bef3a1eda42eb0bc001612

希望能得到一些帮助，如果有人关心并有耐心写个说明and/or一个痕迹，会有所帮助。目前我可以看到答案，但我不明白。

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

Answer 1

异或（异或）的真值table

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

对两个数字进行异或运算只是将两个数字转换为二进制并在真相中应用规则table。

看上面的table，很明显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，其他都相互抵消了。

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

How does xor give different number in two arrays‽

java

functional-programming

bitwise-operators

bit

xor