利用异或运算去除数组中重复的数

在网上看到了2013年的一道小米的笔试题，看到了很多文章都是把代码贴出来了，而对其中蕴含的原理却不是很了解，因而对代码上的理解也很困难。于是就有了本文，希望对和我有同样困惑的读者有帮助。

废话少说，首先先重温一下异或运算的基本知识。
异或运算：一种基于二进制的位运算，特点：同值取0，异值取1.
性质：
交换律： a^b = b^a;
结合律： (a^b)^c = a^(b^c)
对任意的a: a^a = 0; a^0=a; a^(-1) = ~a.

因此，如果有多个数异或，其中由重复的数，不论这些重复的数是否相邻，如果这些数重复了偶数次，则异或后会全部消去；如果重复出现了奇数次，则会保留一个。
这就是理论基础。

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

分析：这个问题，我们只需要将除了重复的数字异或奇数次，其他数字异或偶数次，就可以最后得到这个元素。假设重复的数是n，首先将这1001个元素全部异或一遍，结果用T来表示，即T = 1^2^3^……n^……n^……1000=1^2^3^……1000（T中已经不含n）。然后将T和1到1000这1000个元素都异或一遍，最后的结果就是我们要找的那个元素。
具体编码：

void found(int a[]) {         int xors = 0;         for(int i=0;i<a.length;i++) {             xors ^= a[i];         }         for (int i=0; i< 1000;i++) {             xors ^= i;         }         System.out.println("xors="+xors);     }

再来看看题目2。
题目2：一个数组中只有一个数字出现了一次，其他的全部出现了两次，求出这个数字。

分析：有了上面的基础，是不是感觉很简单。其思路就是把这所有的数都异或一遍，得到的就是我们最后需要的那个数了。


其实上面的题目取了2个极端情况：题目1是只有一个数字重复了2次，而题目2 是只有一个数字出现了1次。而在这之间又可以分化出更多的情况，这也是我们要重点看的一道题目。
题目3：在一个长度为n的整形数组a里，除了三个数字只出现一次外，其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字，程序时间和空间复杂度越小越好。
例如： a = {1,3,7,9,5,9,4,3,6,1,7}，输出4或5或6

分析：可以发现这里和前面2个题目相比，最大的不同就是有3个数只出现了1次。这里就不能单纯的使用上面的结论了。这里需要用到另外一个结论：三个不同的数两两异或得到的三个结果中，肯定有2个结果的低位第一个为1的位置相同。（这三个数总有一个（或2或3个）数的低位第一个为1 的位数从右到左数是最低的，例如是a，a与其他两个数异或的结果低位第一个为1的位数就一定和a的位数相同）
根据这个结论，我们就有办法 取出其中这个不同的数。将这3个异或后的结果分别取最低位中1的位置。然后再将这3个结果都异或，得到其中不同的那个，那么现在用所有原始数据都相互异或 后再分别与每个原始数据异或，取最低位为1的位置 ，如果跟上面相同，那么输出这个数；
假设三个出现一次的数为a,b,c，即把所有的数异或一次，得到的是T=a^b^c。

代码如下：

void find(int a[], int n) {         int i, xors;         xors = 0;         for(i=0;i<n;i++) {             xors ^= a[i];   //得到上面的T         }            int fips = 0;         for(i=0;i<n;++i) {             fips ^= lowbit(xors ^ a[i]); //fips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)         }         int b = 0;         for(i=0;i<n;++i) {             if(lowbit(xors ^ a[i]) == fips)//T与每个元素异或并去最低位，判断是否与fips值相同                 b^=a[i];         }         System.out.println("b="+b);     }

总结：题目3的要求是打印3个数中任意一个数。但是使用这种方式打印出的结果就是这三个数中低位为1位置最小的那个数的值。比如原题中的数组a,则一定会打印5.