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

普通青年解法：

1+2+....+1000->5050

a1+a2+....+a1001->X

x - 5050 -> n(重复)

文艺青年解法：

a1^a2^.....a1001 = n（对所有的元素求一遍异或，就是最终重复的元素）

证明也不复杂，见：

http://www.cnblogs.com/Ivony/archive/2009/07/23/1529254.html

补充：

1、有N＋1个数，N个数出现了偶数次，1个数出现了奇数次，问用O（1）的空间复杂度，找出这两个数。

看了证明就知道，和上面的做法一样，依然是a1^a2^.....a1001 = 数字n，因为偶数次异或抵消

2、有N＋2个数，N个数出现了偶数次，2个数出现了奇数次（这两个数不相等），问用O（1）的空间复杂度，找出这两个数。

参考：http://blog.csdn.net/wodewe/article/details/6863753

假设这两个数为a，b，将数组中所有元素异或结果x=a^b，判断x中位为1的位数（注：因为a！=b，所以x！=0，我们只需知道某一个位为1的位数k，例如0010 1100，我们可取k=2或者3，或者5），然后将x与数组中第k位为1的数进行异或，异或结果就是a，b中一个，然后用x异或，就可以求出另外一个。

为什么呢？因为x中第k位为1表示a或b中有一个数的第k位也为1，假设为a，我们将x与数组中第k位为1的数进行异或时，也即将x与a外加其他第k位为1的出现过偶数次的数进行异或，化简即为x与a异或，结果是b。

void getNum(int a[],int length)
{
	int s=0;//保存异或结果
	for(int i=0;i<length;i++)
	{
		s=s^a[i];
	}
	int temp1=s;//临时保存异或结果
	int temp2=s;//临时保存异或结果
	int k=0;
	while(!(temp1&1))//求位为1的位数
	{
		temp1=temp1>>1;
		k++;
	}
	for(int i=0;i<length;i++)
	{
		if((a[i]>>k)&1)//将s与数组中第k位为1的数异或
		{
			cout<<a[i]<<" ";
			s=s^a[i];
		}
	}
	cout<<s<<" "<<(s^temp2)<<endl;//(s^temp2)用来求另外一个数
}