Series of Xor Arithmetics

先日参加したコンテストにこんな問題が出題されました。排他的論理和を使う問題です。

nとxが与えられる。n個の異なる整数のビットごとに排他的論理和を取ってxとなるようにしたい。n個の非負整数を出力せよ

ただし、1 ≦ n ≦ 10⁵、0 ≦ x ≦ 10⁵とし、出力する非負整数は10⁶までとする

排他的論理和は融通が効く印象がありました。n - 1個の0から始まる連続した整数を用意してそのビットごとの排他的論理和を取り、最後の一個で辻褄を合わせられるんじゃないか? と考えました(その方針の元で実装した解法は無事、システムテストを通過しました!)

排他的論理和の計算は色々なアルゴリズムに登場します。例えばZobrist HashingやRolling Hashを考えるとき、排他的論理和は欠かせません。今回のエントリでは連続した排他的論理和の計算方法について紹介したいと思います。

さて、{1, 0, 0, 1, 0, 1, 0, 1}という数列の排他的論理和を計算することを考えてみましょう。左から演算を行っていくと以下のように計算することができます。

なかなか時間がかかりますね。工夫をしてもっと速く計算できるようにならないでしょうか? 排他的論理和の演算は順序を入れ替えても結果が変わりません。これは利用できないでしょうか?

試しに、先ほどの数列の隣り合った数を入れ替えてみましょう。

先ほどと同様、左から計算します。

無事同じ結果になりました(まあ答えは0か1にしかならないので、あまり説得力がないようにも思えますが...)。

もっと入れ替えれば数列を整列できそうです。具体的には0の数字の集まりと1の数字の集まりにできそうです。

さて、0と0の排他的論理和は0なのでした。つまり、0 xor 0 = 0。また、0 xor 0 xor 0は(0 xor 0) xor 0と計算すればいいので、0 xor 0となります。この結果も0。つまり、0同士の排他的論理和のグループは0と置き換えることができます。

1のかたまりについても同じように工夫ができるでしょうか? 1と1の排他的論理和は0であることを利用すると先ほどの式は以下のようにまとめることができそうです。1の個数が偶数個であれば、0となることが分かります。

1の個数が奇数個である場合も考えてみましょう。

連続した排他的論理和の計算結果は1が偶数個あれば0、1が奇数個あれば1となることが分かります。1の数を数えるだけで演算結果が分かってしまうのです。

もしこれまで、検算などをする場合に最初の図のように左から計算していたのであれば是非この方法も試してみてください。計算の速さはもちろん、正確さが格段に上がるはずです。