题目：一个整型数组里除了3个数字之外，其他的数字都出现了两次。请写程序找出这3个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
这道利用异或的经典面试题目出现很久了，我倒也参考过不少资料，但大部分讲得都比较费解。现在我用大白话来解释一下思路。
1.直接求解该题比较麻烦，不妨先将题目简化，如果只有一个数字是单独出现的，那么我们可以很快想到将数组的所有数字异或一遍，得到的结果就是单独的那个数字：
代码很快可以写出来：
void findOne(int arr[],unsigned int len){
if(arr==NULL || len<1)return;
int i,result = 0;
for (i = 0; i < len; i++){
result ^= arr[i];
}
printf("result = %d \n",result);
}
2.如果是两个数字设为a,b单独出现，直接全部异或得到的结果c是a^b的结果，即 c = a^b ;好像求不出a,b，但是咋们不妨先回忆一下异或的运算规则：
^ 0 1
0 0 1
1 1 0
由于a ≠ b 所以 c ≠ 0，所以c的二进制位一定不全为0，假设二进制位最后一位1出现的位置为 m ，那么对m位而言 a与b的异或结果为 1，显然a与b在该位不同，
eg: a = 2,b=12,c=a^b;
a:0000 0000 0000 0000 0000 0000 0000 0010
b:0000 0000 0000 0000 0000 0000 0000 1100
c:0000 0000 0000 0000 0000 0000 0000 1110
c最后一个1出现的位置为 倒数第2位，在这一位上a为1，b为0
据此可以区分出a与b，不妨假设a的m位为1，那么在数组所有第m位为1的数字中，只有a一个数字是单独出现（其余成对的数字如果在m位为1，那也是成对出现的）！
至此，该问题可以简化为问题 1的情况，找到a后，根据公式： aba = (aa)b = 0^b = b 就可以得到b即： b = c^a;
代码如下：
//只保留num的最后一位的1 其余位为置0
int lastBitOf1(int num){
return num & ~(num - 1);
}
void findTwo(int arr[],int len){
if(arr==NULL || len<1) return;
int i,a=0,b=0,c=0;
for (i = 0; i < len; i++){
c ^= arr[i];
}
int lastZero = lastBitOf1(c);
for (i = 0; i < len; i++){
if( arr[i] & lastZero )
a ^= arr[i];
}
b = c^a;
printf("a=%d \n",a);
printf("b=%d \n",b);
}
3.如果是3个数字设为a,b,c单独出现的情况
看到这里，想必我们自然而然会想到如何找到这三个数字中的区别，据此找到一个数字，然后该问题即可转化为找2个单独出现的数字的问题了。
现在如果也将数组所有数字相互异或，那么得到的将是a,b,c的异或结果，不妨设为 x,即 x = abc，由于a,b,c各不相同则 x ≠ 0
而且有 x^a ≠ 0; x^b ≠ 0 ; x^c ≠ 0
证明如下: 如果 x^a = 0，即 (a^b^c)^a = b^c = 0 则 b == c,与题目矛盾，同理可证明 x^b ≠ 0 ; x^c ≠ 0
那么 lastBitOf1(x^a) lastBitOf1(x^b) lastBitOf1(x^c) 都不为0，为了方便起见，不妨令 fun(n) = lastBitOf1(n); 即 fun(xa)fun(xb)fun(x^c) ≠ 0
不妨令 N = fun(x^a) ^ fun(x^b) ^ fun(x^c), 假设N的最后一位1出现的位置为 pos,
fun(x^a) fun(x^b) fun(x^c) N
0 0 0 0
1 0 0 1
1 1 0 0
1 1 1 1
在第pos位上 fun(xa),fun(xb),fun(x^c) 中有1个或者3个为 1。
假设3个都为1，那么在第pos位 a,b,c都相同且与x不同，
如果在第pos位a,b,c都是0的话 x 在该位的结果为 000 = 0 与假设矛盾
如果在第pos位a,b,c都是1的话 x 在该位的结果为 111 = 1 与假设矛盾
故第pos位上 fun(xa),fun(xb),fun(x^c) 中只有1个1,不妨令 fun(x^a) 在pos位为1 终于找到a,b,c的区别了。
至此，我们可以将这个问题转化为：
数组所有与x的异或的结果的最后一位1出现在pos位的数中只有一位是单独出现的，其余成对出现
这句话有点绕，不妨表达如下
所有满足 fun(arr[i]^x) 的最后一位1出现在第pos位的数中，只有a是单独出现的，其余成对出现
x为数组所有数相互异或的结果 即 x = arr[0]arr[1]...^arr[n-1];
根据问题1的求解我们可以很容易求出a,伪代码如下:
int a= 0;
int i;
for(i=0;i<len;i++){
if(arr[i]^x的最后一位1的位置为pos){
a ^= arr[i];
}
}
再根据问题2的求解我们就可以求出其余的两个数b,c了 。代码如下：
void getThreeUnique(int numbers[], unsigned int len){
if(numbers == NULL || len<1)return;
//辅助数组，找到一个数后，将它放到numbers中，即可转化为findTwo求解
int temp [len+1];
//数组所有数字的异或结果
int xorResult = 0;
int i,flags = 0;
for (i = 0; i < len; i++){
xorResult ^= numbers[i];
temp[i] = numbers[i];
}
for (i = 0; i < len; i++){
flags ^= lastBitOf1(xorResult ^ numbers[i] );
}
// flags为 f(x^a)^f(x^b)^f(x^c)的结果
flags = lastBitOf1(flags);//保留flags最后一位1
int first = 0,second = 0,third = 0;
for (i = 0; i < len; i++){
// x^a,x^c,x^c中 只有1个第m位为1
if( lastBitOf1(numbers[i] ^ xorResult) == flags)
first ^= numbers[i];
}
//找到一个数字后，将它放到原来的数组中，转化为 findTwo 的问题
temp[len] = first;
xorResult ^= first;
flags = lastBitOf1(xorResult);
for (i = 0; i < len+1; i++){
if( temp[i] & flags )
second ^= temp[i];
}
third = xorResult^second;
printf("%d,%d,%d \n",first,second,third);
}
