1. 一个数组中只有一个数字只出现一次，其他所有数字都出现了两次， 请找出这数字。
程序清单1：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> int search(int* arr, int sz); int main(void) { int arr[] = {1,3,4,1,3}; int sz = sizeof(arr) / sizeof(arr[0]); int n = search(arr, sz); printf("%d\n", n); return 0; } int search(int* arr, int sz) { int i = 0; int ret = 0; for (i = 0; i < sz; i++) { ret = ret ^ arr[i]; } return ret; }
如上，创建一个数组：arr [ ] = { 3,3,4,1,1 }
数字1和3出现了一次，数字4出现了两次。
分析：将数字之间两两异或
异或的规则是：同为0，异为1
注意：
int 类型的二进制是32位的数据，而我每个数字只画出了4位，这是为了方便阐述逻辑
那么，根据上面图片，可以找到三个规律
- 0 ^ a = a
- a ^ a = 0
- a ^ a ^ b = a ^ b ^ a
相同元素“抵消”，唯一元素“保留”。
我们再看程序清单1：
分析：
创建一个变量 ret，接着让 ret 与数组中所有的元素异或，两个相同的数字就“抵消”，变成0，剩余的就是单独的数字，即是我们所要找的。
2. 一个数组中只有两个数字只出现一次，其他所有数字都出现了两次， 请找出这两个数字。
程序清单2：
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> void search(int* arr, int sz); int main(void) { int arr[] = { 1,2,1,3,4,3 }; int sz = sizeof(arr) / sizeof(arr[0]); search(arr, sz); return 0; } void search(int* arr, int sz) { int i = 0; int ret = 0; int sign = 0; int s1 = 0; int s2 = 0; //1. 所有元素进行异或，得出 2 ^ 4 = 0110 for (i = 0; i < sz; i++) { ret = ret ^ arr[i]; } //2. 找出sign位置 for (i = 0; i < 32; i++) { if (((ret >> i) & 1) == 1) { sign = i; break; } } //3. 每个数字sign位置 &1 为0 的数组放一起，sign位置 &1 为1 的数组放一起 for (i = 0; i < sz; i++) { if (((arr[i] >> sign) & 1) == 1) { s1 = s1 ^ arr[i]; //得出s1 } } s2 = s1 ^ ret; // 得出s2（s1 ^ s1 ^ s2 = s2） printf("我们要找出的数字是：\n %d %d\n", s1, s2); }
如上，创建一个数组：arr [ ] = { 1,2,1,3,4,3 }
2和4 即是我们所找的数字
分析：
有了程序清单1的规律，我们在其基础上可以找找程序清单2的规律
尝试思路：
1.和程序清单1一样，我们不妨把当前的整个数组都异或一遍
动点脑子，异或的结果指定是 2 ^ 4，因为这两个数字“抵消不了嘛！”
接下来继续分析：
上图我们把数字 2和4 进行异或，结果是 0110，为什么会发生这种情况呢?这是因为两个不一样的数字进行异或，那么异或结果的二进制中，必然有数字1。可以发现：我之所以将上图用蓝色圈出来1，就是因为数字2的二进制，低位第二位是1，而数字4的二进制，低位第二位是0
2.那么，我们第二个思路就有了！就是将这两个数字拆开，然后分组，数字2分到一组，数组4分到另一组，之后按照程序清单1的异或操作就能得出结果啦。分组的依据是什么呢？分组的依据就如思路一所说的，因为两个数字不同，肯定有某个位数不相同。如数字 2和4，我们把二进制第二位是0的分到一组，二进制第二位为1的分到一组不就行了！
然而，道路是曲折的。我们要找的数字是2和4，数字2和数字4 在二进制中，低位第2位是不相同的，那么，如果我们要找的单独数字分别是1和5，情况就不同了。对于数字1和5，他们的前两位相同，低位第3位才是不同的，所以，如果我们进行下一步的编程，所编辑的程序一定要有适应所有的情况！
此时，我们回到程序清单2中的数组中，我决定要把数字 2 ^ 4 结果的 0110 按位与1，并且持续右移操作，直到找出某一位是1的位数，并记下这个位数的位置为sign，那么数字2和数字4 的在sign这个位置一定不一样！接着将数组中的其他元素( 1, 3 )分别按位与1，并且持续右移sign 个位置，这时已经分组完成。
3.最后，我们将第一组的所有元素进行异或，之后也可将第二组的所有元素进行异或。相同元素“抵消”，唯一元素“保留”。
根据上面的图，并参照尝试思路，我们整理三个步骤：
- 将起初数组中的所有元素进行异或，得出 2 ^ 4 = 0110
- 找出 0110 不断右移并按位与1，得出位置sign，此时的sign位置有一个特点：
sign位置可以将要找的两个数字区分开来
- 每个数字sign位置&1为0的数组放一起，sign位置&1为1的数组放一起，最后分别遍历异或，相同元素“抵消”，唯一元素“保留”
输出结果：
总结
此类题目需要非常熟悉位操作及位运算，同时要画图思考，才能将思路整理得很清楚。
或许有很多读者对我提出疑问，他们会认为这只是针对我举例的数组，才会有这种结果。而我想说：
你们可以有时间尝试换一换数组中的元素，并且打乱顺序，也是可以做到的。本篇博客的目的主要是阐明逻辑，因为思路很重要！
Over. 谢谢观看哟~
