异或运算0^0=00^1=11^0=11^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。publicstaticintgetOddTimesNumber(int[]arr){intres=0;对于(inti:arr){res^=i;}返回资源；}例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=1001110001000eor:1001110001000~eor=0110001110111+1=0110001111000&eor:1001110001000=0000000001000记录最右边的1保留，其余1位结果变为0，作为索引。如何利用这个数的特征来区分a和b呢？看这个操作if((x&rightZero)==rightZero){...}valuex和rightZero进行与运算，x的索引会被保留，其他位置清零。在判断语句中，如果判断结果为==rightZero，则会检查x的索引是否为1。用这种方法遍历数组可以解决上面遗留的问题，将a和b分开。遍历数组，使用上面的判断语句，一堆满足条件，一堆不满足条件，a和b肯定是两堆。对一堆满足条件进行异或运算，结果必须是a或b中的一个，eor^得到的数是另一个。让我们看看实现：publicstaticint[]getOddTimesTwoNumber(int[]arr){int[]resArray=newint[2];整数=0;for(inti:arr){eor^=i;}//eor取反加一，然后和eor本身做AND运算，结果会保留eor二进制格式最右边的1，运算后剩下的位都变成0//1001110001000//0000000001000intrightZero=eor&(~eor+1);int首先=0；for(inti:arr){//利用这个条件来区分，将求到的两个数分成两组，if((i&rightZero)==rightZero){first^=i;//过滤器}}resArray[0]=first;resArray[1]=eor^第一；//eor^第一个结果是第二个数returnresArray;}
