异或操作

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

异或操作能够看做无进位相加操作

也就是两个数相加，然而只做加法，不进位。

 1110101 
^1011011 
---------- 
 0101110

运算定律

• 0^a = a, a^a = 0
• 满足交换律 a^b = b^a
• 满足结合律 (a^b)^c = a^(b^c)
• 一堆数异或，无论程序如何，后果雷同，其实就是下面的结合律。

上面来看两道题：

例 1

数组中有一列数字，其中有一个数字 a 呈现了奇数次，其余的数字呈现的次数都是偶数次，求出数字 a, 要求 工夫复杂度是 O(n), 空间复杂度是 O(1)。

剖析：假如这列数字是 aaabbccdddd，程序无所谓，把这些数字进行异或操作，依据第一个定律，两个雷同的数字进行异或后是 0，反复呈现次数为偶数次的数进行异或后都是 0，剩下的 3 个 a，其中两个异或后也是 0，剩下的就是 a，所以也就是说把数组遍历一遍，进行异或操作，最终后果就是要求的数字 a。

    public static int getOddTimesNumber(int[] arr) {
        int res = 0;
        for (int i: arr) {res ^= i;}
        return res;
    }

例 2

数组中有一列数字，其中有两个数字 a 和 b 呈现了奇数次 (a≠b)，其余的数字呈现的次数都是偶数次，求出数字 a 和 b, 要求 工夫复杂度是 O(n), 空间复杂度是 O(1)。
剖析：
1. 把数组遍历一遍进行异或操作后，失去的后果记为 eor，这个 eor 最终肯定是 a^b。
2. 如果能找到一种办法把 a 或者 b 找进去，记为 x，（假如 x 是 a）; 那么 eor^x 就是 b。

利用 O(1)的空间，咱们是没法找的，记录频率必定空间不够哈。那么是否将两者辨别开呢？
因为 a 和 b 不相等，所以 eor 不等于 0，那么其二进制必定有某些地位是 1，或者说至多有一位是 1。那么 a 和 b 的二进制在这个地位处必定不一样（也就是说一个是 1，一个是 0），否则异或后 eor 的该地位肯定是 0。

利用这个察看到的法则，能够把数组中的数分成两组，a 在一组数中，b 在另外一组数中。这里设置为一个未解决的标记，咱们等会儿来解决。

咱们先来看一个位运算的例子：
eor & (~eor + 1)
eor 取反加一，而后和本身进行与运算。来看看失去的后果是什么：

假如 eor = 1001110001000
eor: 1001110001000
~eor=0110001110111
+1  =0110001111000
&eor:1001110001000
=    0000000001000 

失去的是最左边的 1 保留，其余位数变为 0, 这个后果记为 rightZero，1 的地位记为 index.
如何利用这个数字的个性来吧 a 和 b 辨别开来呢？看这个操作
if ((x & rightZero) == rightZero) {...}
数值 x 和 rightZero 进行与操作，就会把 x 的第 index 处保留，其余地位上革除为 0。在判断语句中判断后果是否 ==rightZero 就会查看 x 的 index 处是否为 1。

用这个办法遍历数组，就能够解决下面留的问题，把 a 和 b 离开。遍历数组，用下面的判断语句，符合条件的是一堆，不符合条件的是一堆，而 a 和 b 必定在两个堆中。

把满足条件的一堆，进行异或运算，失去的必定是 a 或 b 其中之一，而拿 eor^ 失去的这个数，失去的就是另一个。

上面来看下实现：

    public static int[] getOddTimesTwoNumber(int[] arr) {int[] resArray = new int[2];
        int eor = 0;
        for (int i: arr) {eor ^= i;}
        // eor 取反加一，而后和 eor 本身进行与运算，后果会把 eor 二进制格局的最左边的 1 保留，其余位变成 0
        // 1001110001000 运算后是
        // 0000000001000
        int rightZero = eor & (~eor + 1);
        int first = 0;
        for (int i: arr) {
            // 以此条件进行辨别，把所求的两个数辨别成两组，if ((i & rightZero) == rightZero) {first ^= i; // 筛选}
        }
        resArray[0] = first;
        resArray[1] = eor ^ first; // eor ^ first 后果就是第二个数
        return resArray;
    }