正式进入高深的算法之前，我们先来学些小技巧。本章拿异或开刀，你会发现一些很有趣的东西。

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。

简单理解就是不进位加法，如1+1=0，,0+0=0,1+0=1。

性质

1、交换律 可任意交换运算因子的位置，结果不变

2、结合律（即(a^b)^c == a^(b^c)）

3、对于任何数x，都有x^x=0，x^0=x，同自己求异或为0，同0求异或为自己

4、自反性 A ^ B ^ B = A ^ 0 = A ，连续和同一个因子做异或运算，最终结果为自己

// 假设存在 a b 两个整数

a = a^b

b = a^b

a = a^b

是不是很神奇，如果不理解，请仔细推算，推算完后脑洞会开一点吧。

奇数二进制的最低位一定是1，偶数二进制的最低位一定是0，所以 a^1==1?偶数:奇数 ，代码就不写了吧。。。脑洞再开

和0做与运算也是可以的a&0==0?偶数:奇数

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现 一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空 间，能否设计一个算法实现？

解法一、显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去（1+2+...+1000）的和。 这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题是，如果数列过大，则可能会导致溢出。

解法二、异或就没有这个问题，并且性能更好。

将所有的数全部异或(1^2^…^1000^k,k为重复数)，得到的结果与(1^2^3^…^1000)的结果进行异或，得到的结果就是重复数。 即(1^2^...^1000^k)^(1^2^3^...^1000)，由于有结合律、交换律存在，我们可以这么调整为(1^1^2^2^...^1000^1000^k)那结果当然就是k了，哈哈哈

google面试题的变形：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数?

结果=a[0]^a[1]^...^a[n-1]

因为奇数个数字连续异或之后是自己，偶数个数连续异或后为0，自己和0异或还是自己。。。真的很神奇

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

套路是一样的，所有元素连续求异或，得到的结果为只出现一次的数字。

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

先试试之前的套路：a[1]^a[2]...^a[n] = a[x]^a[y]，a[x]和a[y]就是这两个数，因为其他数出现偶数次，在异或过程中被自己干掉了（^_^），但是我们得到的结果是a[x]^a[y]，怎么把他俩分开呢？

继续在结果上分析，既然a[x]和a[y]不同，他俩一定在某一个位（记为N）上其中一个是0，其中一个是1（读者仔细想想！），异或值在该位为1，如果找不到这样的差别，二者岂不是相同了？

既然这样，我们可以根据这个性质把数组区分为两个子数组，其中一个子数组（s1）的所有元素在N二进制位上为1，另一个子数组（s2）的所有元素在N二进制位上为0，这样s1必然包含a[x]和a[y]中的一个而s2则包含另一个且s1和s2的元素一定不同（即不会把成对的数分割），分别对两个子数组实施上面的套路（依次连续异或）就会得到两个结果，这两个结果就是最终结果。

伪代码：

xorOfResult = a[1]^a[2]...^a[n]

N = 0

while(true){

if(xorOfResult & (1