您将得到一个大范围的[A，B]，其中“a”和“B”可以是通常为1至40亿（含）之间。你必须找出在给定范围内的所有数字的XOR。
在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（）”的所有数的异或的实际功能是一个辅助功能。
这是一个非常聪明的解决方案 - 它利用这样的事实，有结果的异或运行的模式。所述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）到XOR列表。这是因为所有的高位取消，最低的两位周期每隔4所以，这就是如何在这个小查找表到达。
现在，考虑的一般范围为[A，B]。我们可以用f()找到了XOR [0，A-1]和[0，B]。由于与自身进行XOR运算，任何值为零，f(a-1)正好抵消在XOR中的所有值运行不到a，让你与范围的XOR [A，B]。
添加到FatalError的伟大答案，行return f(b)^f(a-1);可以解释的更好。总之，这是因为XOR有这些奇妙的特性：
这里有两个在行动：
(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c
像这样：
a ^ b = c
c ^ a = b
添加和乘其他关联/可交换操作的两个例子，但他们不扭转自己。好了，那么，为什么这些特性很重要？那么，一个简单的途径是扩大它到它到底是什么，然后就可以看到这些属性在起作用。
首先，让我们来定义我们想要的和正调用它：
n = (a ^ a+1 ^ a+2 .. ^ b)
如果有帮助，认为XOR（^），就好像它是一个补充。
我们还定义函数：
f(b) = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b
b比a更大，所以只是通过一些额外的支架安全下降（我们不能因为它的关联），我们也可以这样说：
f(b) = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)
这简化为：
f(b) = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)
f(b) = f(a-1) ^ n
接下来，我们使用的是反转性质和commutivity给予我们的魔线：
n = f(b) ^ f(a-1)
如果你一直喜欢一个附加思维XOR，你会一直在那里减去下降。 XOR是异或什么补充的是减去！
记住逻辑运算的性能。与他们的工作就像一个相加或相乘，如果有帮助。这种感觉不同寻常，和（），XOR（^）和或（|）是关联的，但他们！
通过先运行幼稚的做法，寻找在输出模式，然后开始寻找其确认该模式是真正的规则。进一步简化您的实现和重复。这可能是原创者所走的路线，通过一个事实，即它不是完全最佳高亮（即使用switch语句，而不是一个数组）。
我发现下面的代码也在努力像这个问题给出的解决方案。
可能是这一点优化，但它只是我从观察重复像接受的答案给出了，
我想知道/了解给定的代码背后的数学证明，如由@Luke布里格斯答案解释
这里是一个JAVA代码
public int findXORofRange(int m, int n) {
int[] patternTracker;
if(m % 2 == 0)
patternTracker = new int[] {n, 1, n^1, 0};
else
patternTracker = new int[] {m, m^n, m-1, (m-1)^n};
return patternTracker[(n-m) % 4];
}
我已经解决了递归问题。我简单地划分成集几乎相等的一部分，每次迭代。
public int recursion(int M, int N) {
if (N - M == 1) {
return M ^ N;
} else {
int pivot = this.calculatePivot(M, N);
if (pivot + 1 == N) {
return this.recursion(M, pivot) ^ N;
} else {
return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N);
}
}
}
public int calculatePivot(int M, int N) {
return (M + N) / 2;
}
让我知道在解决你的看法。高兴得到改进的反馈。提出的解决方案计算出0（日志N）复杂XOR。
谢谢
为了支持XOR从0到N给定所需的代码作如下修改，
int f(int a) {
int []res = {a, 1, a+1, 0};
return res[a % 4];
}
int getXor(int a, int b) {
return f(b) ^ f(a);
}