java - 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

准确的证明，恕我直言，涉及群论(您可以基于xor 构建阿贝尔群):

1. xor是组运算
2. 0 是一个组 0
3. 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