アルゴリズム：範囲内の数値の制約付きXOR

Question

ここでは、数値nが与えられたとしましょう。 [L、R]の範囲にある値の数S ^（S + n）を見つける必要があります。 （Sは負でない整数、^はビット単位のxor演算子です）。

、nが2のべき乗であれば、私は簡単にこれを行うことができます（彼らは非常に便利なパターンを持っている）

私は任意の一般的なn個のためにこれを解決する方法がわからないです。 提案がありますか？

EDIT：

Nも負でない整数です。 n、L、Rはすべて10^18未満です。

これはいくつかの練習テストで私がいつか戻してくれたプログラミング問題でした。私は今、これをStackOverflowで似たような質問を見たことを思い出しました。

EDIT 2： 例で説明するが、 は、n = 1 はその後、我々はSは^（S + 1）は、常にすべてのもののバイナリ表現を持っていることを知っていると言います。例：1,3,7、...

これを解決するには、Range [L、R]内のそのような数値の数を数えなければなりません。

n = 2の累乗であれば、同様の方法が動作します。しかし、nが2のべき乗でない場合、何をするべきか分かりません。

Answer 1

C(n)は、SとしてS^(S + n)と書くことができる（無限の）数字のセットです。

我々持っセット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))から推定できます。 C(n)のすべての要素がnと同じパリティを持ち、したがってC(k)とC(k + 1)が交差しないため、上のunionは実際には分離された和集合です。漸化式の

---

証明：

は単にnとSの最後のバイナリ桁を見てください。