您会得到一个很大的范围 [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()”是一个辅助函数。
这是一个非常聪明的解决方案——它利用了运行 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]
其中第一列是二进制表示，然后是十进制结果及其与 XOR 列表中的索引 (a) 的关系。发生这种情况是因为所有高位都取消了，而最低两位每 4 位循环一次。所以，这就是到达那个小查找表的方法。
现在，考虑 [a,b] 的一般范围。我们可以f()用来求 [0,a-1] 和 [0,b] 的 XOR。由于任何与自身异或的值都为零，因此f(a-1)只需取消 XOR 中小于 的所有值a，从而为您留下范围 [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：
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
接下来，我们使用反转属性和交换性来给我们一条神奇的线：
n = f(b) ^ f(a-1)
如果您一直将 XOR 视为加法，那么您将在那里进行减法。XOR 是 XOR 加是减！
记住逻辑运算符的属性。如果有帮助的话，几乎可以像加法或乘法一样使用它们。and (&)、xor (^) 和 or (|) 是关联的，这感觉很不寻常，但它们是！
首先运行简单的实现，在输出中查找模式，然后开始查找确认模式为真的规则。进一步简化您的实施并重复。这可能是最初创建者采用的路线，突出显示它不是完全最优的事实（即使用 switch 语句而不是数组）。
我发现下面的代码也像问题中给出的解决方案一样工作。
可能这有点优化，但这正是我从观察到的重复中得到的，就像在接受的答案中给出的那样，
我想知道/理解给定代码背后的数学证明，就像@Luke Briggs 在回答中解释的那样
这是那个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(log N) 复杂度计算 XOR。
谢谢
为了支持从 0 到 N 的 XOR，需要修改给定的代码，如下所示，
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);
}
进一步补充 FatalError 的答案，可以证明（通过归纳）观察到的模式f()将每 4 个数字循环一次。
我们试图证明对于每个整数k >= 0，
f(4k + 1) = 1
f(4k + 2) = 4k + 3
f(4k + 3) = 0
f(4k + 4) = 4k + 4
f(n)在哪里1 ^ 2 ^ ... ^ n。
作为我们的基本情况，我们可以手工计算出
f(1) = 1
f(2) = 1 ^ 2 = 3
f(3) = 3 ^ 3 = 0
f(4) = 0 ^ 4 = 4
对于我们的归纳步骤，假设这些方程在特定整数4x（即f(4x) = 4x）之前为真。我们想证明我们的方程对于4x + 1、4x + 2和是正确4x + 3的4x + 4。
为了帮助编写和可视化证明，我们可以让b(x)表示 的二进制（base-2）字符串表示， x例如。
b(7) = '111'b(9) = '1001'
和
b(4x) = 'b(x)00'
b(4x + 1) = 'b(x)01'
b(4x + 2) = 'b(x)10'
b(4x + 3) = 'b(x)11'
这是归纳步骤：
Assume: f(4x) = 4x = 'b(x)00'
Then:
f(4x + 1) = f(4x) ^ (4x + 1) // by definition
= f(4x) ^ 'b(x)01' // by definition
= 'b(x)00' ^ 'b(x)01' // from assumption
= '01' // as b(x) ^ b(x) = 0
f(4x + 2) = f(4x + 1) ^ (4x + 2)
= f(4x + 1) ^ 'b(x)10'
= '01' ^ 'b(x)10'
= 'b(x)11' // this is 4x + 3
f(4x + 3) = f(4x + 2) ^ (4x + 3)
= f(4x + 2) ^ 'b(x)11'
= 'b(x)11' ^ 'b(x)11'
= '00'
For the last case, we don't use binary strings,
since we don't know what b(4x + 4) is.
f(4x + 4) = f(4x + 3) ^ (4x + 4)
= 0 ^ (4x + 4)
= 4x + 4
因此，该模式适用于 之后的接下来的四个数字4x，从而完成了证明。