算法:范围内数字的约束异或

Question

假设给定了一个数字 n。我们需要找到 [L, R] 范围内的值 S ^ (S+n) 的个数。(其中 S 是任何非负整数，^ 是按位异或运算符)。

如果 n 是 2 的幂，我可以很容易地做到这一点(他们有一个非常有用的模式)

我不确定如何为任何一般 n 解决这个问题。有什么建议吗？

编辑:

n 也是一个非负整数。n、L、R均小于10^18。

这是我在某个练习测试中给出的一个编程问题，我只是记得今天在 StackOverflow 上看到了一个类似的问题。

编辑 2:举例说明，假设 n = 1。然后我们知道 S ^ (S + 1) 将始终具有所有 1 的二进制表示。例如:1,3,7,...

所以解决这个问题很容易，我们只需要计算范围 [L,R] 内的此类数字的数量，这非常简单。

对于 n = 2 的任何幂，类似的方法都有效。但是如果 n 不是 2 的幂，我不知道该怎么办。

Answer 1

让C(n)是可以写成 S ^ (S + n) 的(无限)数字集对于一些 S .

我们在集合 C(n) 上有以下递推关系:

• 如果n = 2k是偶数，则C(n) = {2x : x in C(k)} ;
• 如果n = 2k + 1是奇数，那么 C(n) = {2x + 1 : x in C(k)} union {2x + 1 : x in C(k + 1)} .

可以从这些关系中推导出一个算法。更准确地说，一对 (C(n), C(n + 1))可以从(C(n / 2), C(n / 2 + 1))推导出来.请注意 union上面实际上是一个不相交的联合，因为 C(n) 中的每个元素与 n 具有相同的奇偶校验，因此 C(k)和 C(k + 1)不相交。

---

递归关系的证明:

简单看一下n的最后二进制数和 S .