异或操作

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;
    }