algorithm - 查找给定范围内所有数字的 XOR

Question

给定一个很大的范围 [a,b]，其中“a”和“b”通常介于 1 到 4,000,000,000 之间(含)。您必须找出给定范围内所有数字的异或。

这个问题在 TopCoder SRM 中使用过。我看到了比赛中提交的其中一个解决方案，但我无法弄清楚它是如何工作的。

谁能帮忙解释一下获胜的解决方案:

long long f(long long a) {
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

这里，getXor() 是计算传入范围 [a,b] 中所有数字的异或的实际函数，而“f()”是辅助函数。

Answer 1

这是一个非常聪明的解决方案——它利用了在运行的 XOR 中存在结果模式这一事实。 f() 函数从 [0, a] 计算 XOR 总运行。查看此表以了解 4 位数字:

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

其中第一列是二进制表示，然后是十进制结果及其与异或列表中索引 (a) 的关系。发生这种情况是因为所有高位都取消并且最低两位每 4 次循环一次。所以，这就是如何得出那个小查找表。

现在，考虑 [a,b] 的一般范围。我们可以使用 f() 找到 [0,a-1] 和 [0,b] 的 XOR。由于任何与自身异或的值都是零，f(a-1) 只是抵消了 XOR 运行中小于 a 的所有值，剩下的就是范围 [a,b] 的异或。