XOR 究竟是如何工作的，它背后的魔力是什么？

Question

这个问题可能有点误导，但我不知道如何用另一种方式提问。 hackerrank 中存在如下问题：

Consider an array of integers, where all but one of the integers occur in pairs. In other words, every element in occurs exactly twice except for one unique element.

Given the array find and print the unique element. [2,3,1,3,2] -> result is 1

我是这样解决问题的：

private static int lonelyInteger(int[] a) {
        if(a==null)
            return 0;

         if(a.length<2)
             return a.length;

        Set<Integer> set = new HashSet<>();

        for(int i : a){

            if(set.contains(i)){
                set.remove(i);
            }else{
                set.add(i);
            }            
        }

        return (Integer) set.toArray()[0];
    }

然而我们发现这个问题有一个巧妙的解决方案，那就是：

private static int lonelyInteger(int[] a) {
         int b = a[0];

         for(int i = 1; i < a.length; i++){
             b ^= a[i];
         }
        return b;       
    }

问题是我不知道它为什么有效？！我了解它是如何工作的，但不明白它为什么工作？理解我做了一个小程序输出每一步的结果：

public class BitwiseOperator {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        int sum = 0;
        in.nextLine();
        String line = in.nextLine();
        String[] numbers = line.split(" ");
        for (int i = 0; i < numbers.length; i++) {
            a[i] = Integer.valueOf(numbers[i]);
        }

        for (int i = 0; i < a.length; i++) {
            binary(sum, a[i]);
            sum ^= a[i];
            binary(sum);
            System.out.println();
            System.out.println();
            System.out.println();

        }
        System.out.println(sum);
    }


    private static void binary(int sum) {
        System.out.println(String.format("%16s", Integer.toBinaryString(sum)).replace(' ', '0') + " ->" + sum);
    }

    private static void binary(int sum, int i) {
        System.out.println(String.format("%16s", Integer.toBinaryString(sum)).replace(' ', '0') + " ->" + sum);
        System.out.println("XOR");
        System.out.println(String.format("%16s", Integer.toBinaryString(i)).replace(' ', '0') + " ->" + i);
        System.out.println("--------");
    }


}

如果输入以下输入：

5

2 3 2 1 3

输出为：

0000000000000000 ->0
XOR
0000000000000010 ->2
--------
0000000000000010 ->2



0000000000000010 ->2
XOR
0000000000000011 ->3
--------
0000000000000001 ->1



0000000000000001 ->1
XOR
0000000000000010 ->2
--------
0000000000000011 ->3



0000000000000011 ->3
XOR
0000000000000001 ->1
--------
0000000000000010 ->2



0000000000000010 ->2
XOR
0000000000000011 ->3
--------
0000000000000001 ->1



1

所以该程序确实有效，但我真的需要了解为什么？

Answer 1

考虑一个整数数组，其中除一个整数外的所有整数都成对出现。换句话说，除了一个独特的元素外，其中的每个元素都恰好出现两次。现在假设您将所有这些数字相加。

这个和是偶数是什么意思？意思是出现一次的数一定是偶数。如果这个和是奇数，这意味着什么？意思是出现一次的数一定是奇数。想一想，直到你明白为止。

现在想象一下，我们不是对它们求和，而是跟踪总和是偶数还是奇数。所以如果前两个数字是 3 和 7，总和就是 10，但我们只记得它是偶数。这仍然有效。最后的答案是即使出现一次的数字是偶数，如果出现一次的数字是奇数则为奇数。想一想，直到你明白为止。

这就是我们如何让它适用于其中的一位数字。但我们也可以同时对所有位执行此操作，跟踪每个位的位置是总数是奇数还是偶数。完成后，我们将知道每个位位置出现一次的数字是奇数还是偶数，这就是我们所需要的。因为我们是用二进制来做的，所以那个位置唯一的奇数是 1，唯一的偶数是 0。想想这个直到你理解它。

Answer 2

准确的证明，恕我直言，涉及群论（你可以建立阿贝尔群基于xor）：

xor是组操作
0是一组0
A 是一个逆元素（所以任何 A 都是它自身的逆元素）。

当然要证明(A xor B) xor C == A xor (B xor C)

因为 A xor B == B xor A 我们有一个 阿贝尔群 这就是为什么可以重组任意顺序的项目：

  A XOR B XOR C XOR A XOR B ==
 (A XOR A) XOR (B XOR B) XOR C ==
  C

一般情况下：

   A xor B xor ... xor Z ==
  (A xor A) xor (B xor B) xor ... xor (distinct Item) ==
   0 xor 0 xor ... xor (distinct Item) ==
   distinct Item

Answer 3

我会尽量保持简短。

异或同一个数returns 0.

示例： 23^23 = 0 -325 ^ -325 = 0

所以当你运行通过循环异或时，出现两次的数字会自行抵消，最后你会得到唯一的数字。

XOR 究竟是如何工作的，它背后的魔力是什么？

How does XOR really works, and what is the magic behind it?

java

algorithm

binary

bitwise-operators