问题：求1到n这n个整数间的异或值，即 1 xor 2 xor 3 ... xor n
记 f(x, y) 为x到y的所有整数的异或值。
对 f(2^k, 2^(k+1) -1) (注意文章中的 ^ 表示的是“幂”，xor 表示“异或”，or 表示“或”)：
2^k 到 2^(k+1) -1 这2^k个数，最高位（+k位）的1个数为2^k，
若 k >= 1，则2^k为偶数，将这2^k个数的最高位(+k位)去掉，异或值不变。
因而 f(2^k, 2^(k+1) -1) = f(2^k - 2^k, 2^(k+1) -1 -2^k) = f(0, 2^k -1)
因而 f(0, 2^(k+1) -1) = f(0, 2^k -1) xor f(2^k, 2^(k+1) -1) = 0 (k >= 1)
即 f(0, 2^k - 1) = 0 (k >= 2)
对 f(0, n) (n >= 4) 设n的最高位1是在+k位(k >= 2)，
f(0, n) = f(0, 2^k - 1) xor f(2^k, n) = f(2^k, n)
对2^k到n这n+1-2^k个数，最高位(+k位)共有 m = n+1-2^k 个1,去除最高位的1
当n为奇数时，m是偶数，因而 f(0, n) = f(2^k, n) = f(0, n - 2^k)
由于n - 2^k 与 n同奇偶，递推上面的公式，可得：f(0, n) = f(0, n % 4)
当 n % 4 == 1 时， f(0, n) = f(0, 1) = 1
当 n % 4 == 3 时， f(0, n) = f(0, 3) = 0
当n为偶数时，m是奇数，因而 f(0, n) = f(2^k, n) = f(0, n - 2^k) or 2^k
也就是说，最高位1保持不变，由于n - 2^k 与 n同奇偶，递推上面的公式，
可得：f(0, n) = nn or f(0, n % 4) (nn为 n的最低2位置0)
当 n % 4 == 0 时， f(0, n) = n
当 n % 4 == 2 时， f(0, n) = nn or 3 = n + 1 （公式对 n = 2仍成立）
综上所述：
f(1, n) = f(0, n) =
n n % 4 == 0
1 n % 4 == 1
n +1 n % 4 == 2
0 n % 4 == 3
代码：
unsigned xor_n(unsigned n)
{
unsigned t = n & 3;
if (t & 1) return t / 2u ^ 1;
return t / 2u ^ n;
}
作者： flyinghearts
出处： http://www.cnblogs.com/flyinghearts/
本文采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议进行许可，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。