查找给定范围内所有数字的XOR
你会得到一个很大的范围[a，b]，其中'a'和'b'通常可以在1到4,000,000,000之间。 你必须找出给定范围内所有数字的XOR。
TopCoder SRM使用了这个问题。 我看到比赛中提交的一个解决scheme，我无法弄清楚它的工作原理。
有人可以帮助解释获奖的解决scheme：
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]中所有数的xor的实际函数，“f（）”是辅助函数。
这是一个非常聪明的解决scheme – 它利用了运行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）的关系到XOR列表中。 发生这种情况的原因是所有的高位都被取消，而最低的两位每4位就循环一次。所以，这就是如何到达这个小查找表的问题。
现在考虑[a，b]的一般范围。 我们可以用f()来find[0，a-1]和[0，b]的XOR。 由于XOR与自身的任何值都是零，所以f(a-1)只是将XOR运行中的所有值都取消为小于a ，而将范围[a，b]的XOR留给您。
添加到FatalError的很好的答案，行return f(b)^f(a-1); 可以更好地解释。 简而言之，这是因为异或拥有这些奇妙的属性：
- 它是联想 – 放置括号，无论你想要的
- 这是交换 – 这意味着你可以移动运营商（他们可以“通勤”）
这两个在行动：
(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
接下来，我们使用逆转属性和交stream来给我们带来神奇的线条：
n = f(b) ^ f(a-1)
如果你一直在想XOR就像是一个加法，那么你会在这里减去一个。 XOR是XOR加减法！
我如何自己想出这个呢？
记住逻辑运算符的属性。 与他们一起工作，如果有帮助，几乎就像是增加或增加一样。 （＆），xor（^）和or（|）是联合的，但它们是！
首先运行天真的实现，在输出中寻找模式，然后开始寻找确认模式为真的规则。 简化您的实施，甚至进一步和重复。 这可能是原始创build者所采用的路线，由于它不是完全最佳的（即，使用开关语句而不是数组）而突出显示。
我发现下面的代码也像问题中给出的解决scheme一样工作。
可能这是一个小优化，但它正是我所得到的观察重复在接受的答案中给出的，
我想知道/理解给定代码背后的mathcertificate，就像@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[(nm) % 4]; }
