给你一个很大的范围[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]中所有数字的xor的实际函数,"f()"是辅助函数.
可能重复:
在数组中查找缺失数字的最快方法
输入:未排序的数组A [1,..,n],其中包含0,...,n范围内的除整数之外的所有整数
问题是在O(n)时间内确定缺失的整数.A的每个元素以二进制表示,唯一可用的操作是函数位(i,j),它返回A [i]的第j位的值并占用恒定时间.
有任何想法吗？我认为某种分而治之的算法是正确的,但我想不出我应该做什么.提前致谢!
这里每行包含一个数字的位表示.这些数字来自1..N正好缺少一个数字.找到缺失数字的位表示.
面试官问我这个问题.
我说:"我们可以找到给定数字的总和,并从前n个数字的总和中减去它(我们知道为(N*(N + 1))/ 2)"
他说这涉及从基数10变为2.
你能否给我一个如何在不改变基础的情况下解决问题的提示？