算法：范围内数字的约束异或
Algorithm: constrained XOR of numbers within a range
假设给定了一个数字 n。
我们需要找到 [L, R] 范围内的值 S ^ (S+n) 的个数。
（其中 S 是任何非负整数，^ 是按位异或运算符）。
如果 n 是 2 的幂，我可以很容易地做到这一点（他们有一个非常有用的模式）
我不确定如何为任何一般 n 解决这个问题。
有什么建议吗？
编辑：
n也是一个非负整数。
n、L、R均小于10^18.
这是我在某个练习测试中给出的编程问题，我只是记得今天在 Whosebug 上看到了类似的问题。
编辑 2：
举例说明，
假设 n = 1。
然后我们知道 S ^ (S + 1) 将始终具有所有 1 的二进制表示。例如：1,3,7,...
所以解决这个问题很容易我们只需要计算[L,R]范围内这样的数字的数量就很简单了。
对于 n = 2 的任意幂，类似的方法都有效。但是我不知道如果 n 不是 2 的幂怎么办。
设 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的最后二进制数。
假设给定了一个数字 n。 我们需要找到 [L, R] 范围内的值 S ^ (S+n) 的个数。 （其中 S 是任何非负整数，^ 是按位异或运算符）。
如果 n 是 2 的幂，我可以很容易地做到这一点（他们有一个非常有用的模式）
我不确定如何为任何一般 n 解决这个问题。 有什么建议吗？
编辑：
n也是一个非负整数。 n、L、R均小于10^18.
这是我在某个练习测试中给出的编程问题，我只是记得今天在 Whosebug 上看到了类似的问题。
编辑 2： 举例说明， 假设 n = 1。 然后我们知道 S ^ (S + 1) 将始终具有所有 1 的二进制表示。例如：1,3,7,...
所以解决这个问题很容易我们只需要计算[L,R]范围内这样的数字的数量就很简单了。
对于 n = 2 的任意幂，类似的方法都有效。但是我不知道如果 n 不是 2 的幂怎么办。
设 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的最后二进制数。