C++で範囲[L, R]内のすべての要素のXORを効率的に求める方法

この記事では、2つの整数 L と R で表される範囲が与えられたとき、その範囲 [L, R] 内に含まれるすべての整数のXOR(排他的論理和)を求める方法を解説します。

問題の例

入力: L = 3, R = 6

出力: 4

説明: 3 ^ 4 ^ 5 ^ 6 = 4

解法のアプローチ

この問題を解くには、まず R の最上位ビット(MSB) を求めます。答えとなるXOR値のMSBは、RのMSBを超えることはありません。次に、0からMSBまでの各ビット位置 i について、範囲内でそのビットが立っている数の個数のパリティ(偶奇)を調べます。

i 番目のビットに着目すると、そのビットの状態は 2ⁱ 個ごとの数で変化することがわかります。この性質は、範囲 L 〜 R 内の i 番目のビットがセットされたすべての数に当てはまります。これを踏まえると、以下の2つの場合に分けて考えることができます。

ケース1(i ≠ 0 の場合)

まず L の i 番目のビットを確認します。このビットがセットされている場合は、L から L + 2ⁱ までの間の数のパリティを調べます。L の i 番目のビットがセットされていて L が奇数であれば、そのカウントは奇数になり、そうでなければ偶数になります。同様に R 側についても、R − 2ⁱ から R までの要素数のパリティを同じ方法で判定します。

それ以外の整数は考慮する必要がありません。これらは i 番目のビットがセットされた整数を偶数個しか生成しないため、XORの結果に影響を与えないからです。

ケース2(i = 0 の場合)

最下位ビットについては、以下の2つの場合を考慮します。

ケース2.1: L と R がどちらも奇数の場合、0番目のビットがセットされた整数の個数は (R − L) / 2 + 1 となります。

ケース2.2: それ以外の場合、個数は (R − L + 1) / 2 の切り捨て値となります。

実装例(C++)

上記の解法を実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;
int findMSB(int x) {
    int ret = 0;
    while ((x >> (ret + 1)) != 0)
        ret++;
    return ret;
}
int XOREleInRange(int L, int R) {
    int max_bit = findMSB(R);
    int mul = 2;
    int ans = 0;
    for (int i = 1; i <= max_bit; i++) {
        if ((L / mul) * mul == (R / mul) * mul) {
            if (((L & (1 << i)) != 0) && (R - L + 1) % 2 == 1)
                ans += mul;
            mul *= 2;
            continue;
        }
        bool oddCount = 0;
        if (((L & (1 << i)) != 0) && L % 2 == 1)
            oddCount = (oddCount ^ 1);
        if (((R & (1 << i)) != 0) && R % 2 == 0)
            oddCount = (oddCount ^ 1);
        if (oddCount)
            ans += mul;
        mul *= 2;
    }
    int zero_bit_cnt = zero_bit_cnt = (R - L + 1) / 2;
    if (L % 2 == 1 && R % 2 == 1)
        zero_bit_cnt++;
    if (zero_bit_cnt % 2 == 1)
        ans++;
    return ans;
}
int main(){
    int L = 1, R = 4;
    cout<<"The XOR of all element within the range ("<<L<<", "<<R<<") is : "<<XOREleInRange(L, R);
    return 0;
}

実行結果

The XOR of all element within the range (1, 4) is : 4

まとめ

このアルゴリズムは、範囲内のすべての数を順番にXORしていく素朴な手法(O(R − L)の計算量)と異なり、ビット演算の性質を活用することで O(log R) の計算量で結果を求められます。そのため、非常に大きな範囲が与えられた場合でも高速に動作するのが大きな特徴です。