题目：
数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次。写一个函数，找出被重复的数字。
异或法
数组a[N]中的N个数异或结果与1至N-1异或的结果再做异或，得到的值即为所求。
- 设重复数为A，其余N-2个数异或结果为B。
- N个数异或结果为A^A^B
- 1至N-1异或结果为A^B
- 由于异或满足交换律和结合律，且X^X = 0 0^X = X;
- 则有
- (A^B)^(A^A^B)=A^B^B=A
最近看了比较多的面试题，其中有还有其他的变种是这样的：
1、一个数组中有一堆数字，每个数字都重复出现了一次，除了其中一个，求出这个数字是什么。
2、一个数组中有一堆数字，每个数字都重复出现了一次，除了其中两个，求出这两个数字是什么。
3、一个数组中有一堆数字，每个数字都重复出现了一次，除了其中三个，求出这三个数字是什么。
这三个题目，想要快速得到结果，就是用异或的算法。
对于1，数组中所有数字异或起来之后就得到了这个数字。
对于2，所有数字都异或起来之后，得到的是那两个目标数字的异或结果，由于这两个数字是绝对不相同的，所以异或结果必然不为0.也即是必然其二进制会有一位是1，假设是第k位，那么对于第k位，必然有一些数字是0，有一些是1。那么，根据第k位是不是1，可以将原来数组分成两半，每一半分别异或起来，会得到两个结果，就是我们要找的两个数字了。
对于3，何海涛的163博客里面有讲。这个比较复杂，但是思路还是利用针对2的方法。