找到所有的数字XOR在给定的范围内 [英] Find XOR of all numbers in a given range

问题描述

您将得到一个大的范围是[A，B]，其中A和B可以是通常在1和40亿包。你必须找出所有号码的XOR在给定的范围内。

You are given a large range [a,b] where 'a' and 'b' can be typically between 1 and 4,000,000,000 inclusive. You have to find out the XOR of all the numbers in the given range.

这个问题被用在顶部codeR SRM。只见提交在比赛中的解决方案之一，我无法弄清楚如何其工作。

This problem was used in TopCoder SRM. I saw one of the solutions submitted in the match and I'm not able to figure out how its working.

有人能帮助解释殊荣的解决方案：

Could someone help explain the winning solution:

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（）的异或为一个帮手功能。

Here, getXor() is the actual function to calculate the xor of all number in the passed range [a,b] and "f()" is a helper function.

推荐答案

这是一个pretty的聪明的解决方案 - 它利用的事实，那就是结果在运行异或模式。该 F（）函数计算在[0，A]异或总运行。看看这个表4​​位号码：

This is a pretty clever solution -- it exploits the fact that there is a pattern of results in the running XORs. The f() function calculates the XOR total run from [0, a]. Take a look at this table for 4-bit numbers:

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]

当第一列是二进制重新presentation然后小数结果及其与它的索引（一个）插入异或列表。这是因为所有的高位取消，最低的两位周期的每个4.所以，这就是如何在这个小查找表到达。

Where the first column is the binary representation and then the decimal result and its relation to its index (a) into the XOR list. This happens because all the upper bits cancel and the lowest two bits cycle every 4. So, that's how to arrive at that little lookup table.

现在，考虑了一般范围[A，B]。我们可以使用 F（）找到XOR为[0，A-1]和[0，B]。由于XOR运算与自身的任何值是零， F（A-1）只是取消了在异或的所有值运行不到 A ，离开你，范围是[A，B]。

Now, consider for a general range of [a,b]. We can use f() to find the XOR for [0,a-1] and [0,b]. Since any value XOR'd with itself is zero, the f(a-1) just cancels out all the values in the XOR run less than a, leaving you with the XOR of the range [a,b].

这篇关于找到所有的数字XOR在给定的范围内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！