[解決済み] 与えられた範囲にあるすべての数値のXORを求めよ

質問

a'と'b'が1〜4,000,000,000の範囲にある大きな範囲[a,b]が与えられている。あなたは与えられた範囲内のすべての数値の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()"はヘルパー関数です。

どのように解決するのですか？

これはかなり巧妙な解決策です。実行中の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]

最初の列は2進数表現で、次に10進数の結果とXORリストのインデックス(a)との関係です。 これは、すべての上位ビットがキャンセルされ、下位2ビットが4ごとに循環するためです。このようにして、小さなルックアップテーブルができあがるわけです。

さて、[a,b]の一般的な範囲について考えてみましょう。この場合 f() を使って [0,a-1] と [0,b] の XOR を求めます。自分自身とXORした値はすべて0になるので f(a-1) よりも小さい XOR ランの値をすべて打ち消すだけです。 a よりも小さい値をすべてキャンセルし、範囲 [a,b] の XOR を残します。