问题定义：有2n+1个数，只有一个单着，别的都是成对的，找出这个单着的数。比如：2 1 3 2 1。3是答案。
思路一：暴力搜索——每个数都和其他数比较，找不到相同的，就得到了结果。时间复杂度为o(n2)
思路二：排序搜索——先给序列排个序，之后从前往后一对一对的找，直到不是成对的为止。时间复杂度，怎么也得o(nlgn)
思路三：异或计算，一趟搞定。时间复杂度o(n)
直接看思路三：
原理：异或操作（^）——（对于位操作）相同为0，相异为1.比如：1^0 = 1, 1 ^1=0
这样：
- 两个相同的数异或就为0
- 任何数和0异或为自己（转化到位。1^0 = 1, 0 ^0=0）
例如：5 ^ 5 = 0
5 ^ 0 = 5
对于本题：2 1 3 2 1，都异或一下：相同的（2^2,1^1） 为0，剩下的3和0异或为自身3。(注：异或具有交换律)
参考代码：
#include <stdio.h> int main() { int a[5] = {2, 1, 3, 2, 1}; int aim = a[0]; for(i = 1; i < 5; i++) { aim = aim ^ a[i]; } printf("Result:", aim); return 0; }
异或在这方面挺好，再来个应用：
不用第三个数直接交换两个数：
#include <stdio.h> void swap(int *a, int *b) { *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } int main() { int a=3, b=5; swap(&a, &b); printf("%d\n%d", a, b); return 0; }
当然完成这个题目还可以用同样的思维：
#include <stdio.h> void swap(int *a, int *b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; } int main() { int a=3, b=5; swap(&a, &b); printf("%d\n%d", a, b); return 0; }
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/04/03/2998829.html，如需转载请自行联系原作者
