查找给定范围内所有数字的异或

  • Z时代
  • 2024-01-10
  • 分类：问答

您将获得较大的[a，b]范围，其中“ a”和“ b”通常可以在1到4,000,000,000之间（含）。您必须找出给定范围内所有数字的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（）”是一个辅助函数。

回答：

这是一个非常聪明的解决方案-它利用了一个事实，即正在运行的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运算的值均为零，因此Just会抵消XOR运算中所有小于的值a，从而使您具有[a，b]范围的XOR。

以上是 查找给定范围内所有数字的异或 的全部内容， 来源链接： utcz.com/qa/420102.html

回到顶部