异或巧妙求解唯一数

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

先来看一下异或的运算法则

1. a ⊕ a = 0
2. a ⊕ 0 = a
   通过位运算的话，就是相同为0，不同为1，如下表
   a b a⊕b
   1 0 1
   1 1 0
   0 0 0
   0 1 1
3. a ⊕ b = b ⊕ a
4. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
5. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.
6. a ⊕ b ⊕ a = b.
   满足12交换律和结合律，(12是为了去和谐zujiao)

本题中除了两个出现的一次的元素，其他的元素都出现两次，那么出现两次的元素能够自己与自己相 异或 掉，也就是把数组中所以元素逐一异或，最终的结果就是出现一次 的 那两个元素的异或结果。
a⊕b⊕c⊕f⊕d⊕a⊕e⊕c⊕b⊕d = a⊕a ⊕ b⊕b ⊕ c⊕c ⊕ d⊕d f⊕e = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ f⊕e = f⊕e

如果只出现一次的元素只有一个，是不是一次异或运算就可以找出来，但是本题是两个，那就想办法把这两个出现一次的元素分到不到的类别里，然后在不同的类别里进行异或运算，最后的结果就是该类别里 出现一次的元素。所以需要构造一个分类器。

这 出现一次的 两个元素 异或结果：_OR，这个结果的 二进制位 为1的 肯定包含了两个元素的不同位（0⊕1=1），异或结果_OR 与 自身的补码 相与的结果 为1的位 就是这两个元素第一个不同位（其他位都会为0），该结果作为分类器classify = _OR & (- _OR)，该分类器 分别 & 这两个元素，一个为0，一个不为0，即可分到不同类别中去。

ex:
3 ⊕ 6 = 0011 ⊕ 0110 = 0101 = _OR
-_OR = 1011
_OR & (- _OR) = 0101 & 1011 = 0001 = classify
classify & 3 = 0001 & 0011 = 0001
classify & 6 = 0001 & 0110 = 0000

最后的代码就很清晰明了 了！

public static void findNumsAppearOnce(int[] array,int num1[] , int num2[]) {
        if(null == array) return;
        int _OR = 0;
        for (int arr:array) {
            // 最终异或的结果 为两个出现一次的数 的异或 结果
            _OR ^= arr;
        }
        // 分类器
        int classify = _OR & (- _OR);
        for (int arr:array) {
            int condition = arr & classify;
            if(condition == 0) {
                num1[0] ^= arr;
            } else num2[0] ^= arr;
        }
    }