关于异或的一个有趣的现象

今天无意之中发现了一个关于异或运算的一个有趣的现象。

假设函数f(n)是自然数1，2，3,...,n的所有数的异或，即f(n)=1^2^3^...^n, 那么，任意的n（n为自然数），我们能够很快的计算出f(n)的值
  

if n == 4*m, then f(n) = n
else if n == 4*m + 1, then f(n) = 1
else if n == 4*m + 2, then f(n) = n+1
else   n = 0

其中m为整数，哈哈这个公式是不是很简单呢？公式的证明可以采用数学归纳法，这儿就不啰嗦了。

另外，异或的一些基本的性质：

1. 交换律
2. 结合律
3. x^x = 0, 0^x=x, a^b^a=b

利用异或的这些性质，我们可以在不需要任何额外空间的情况下交换两个变量的值：
方法如下：利用异或交换整数a，b的值

a ^= b;
b ^= a;
a ^= b;

是不是看上去很绕啊？ 其实原理很简单，

new_b = (a^b)^b = a^b^b = a^(b^b) = a^0 = a
new_a = (a^b)^a = a^b^a = a^a^b = (a^a)^b = 0^b = b

这下明白了吧？

一道有趣的题目：

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

这题一个很简单的解法是将1001个数相加再减去1-1000的和，但是如果数据更大可能导致计算的和太大而溢出。 但是如果用异或运算则不会有这个担心，方法也很简单，可以先想一想了。

方法： 将1001个数进行异或，在与1-1000的异或进行异或。 即 x = (1001个数的异或）^ (1^2^3^...^1000), 计算1-1000的异或就可以采用我上面提到的公式了，很简单的。

下面一道更加复杂一点的题目：

有N个整数，除了其中的两个数只出现一次以外，其余的所有的数都正好出现两次，如何用最快的方法求出只出现一次的两个数，要求空间复杂度是O(1).

大家可以思考一下。