C++で指定範囲内の2整数から最大XOR値を求めるアルゴリズム

問題の概要

範囲 [L, R] が与えられたとき、この範囲内から2つの整数を選び、そのXOR(排他的論理和)が考えられるすべての組み合わせの中で最大となるようにする問題です。

例として、L = 1、R = 21 が与えられた場合を考えてみましょう。このとき出力は 31 になります。

これは、15 XOR 16 = 31 となり、範囲内のどの2整数の組み合わせよりも大きなXOR値になるためです。

アルゴリズム

この問題は、全組み合わせを総当たりで調べなくても、ビット演算の性質を使えば効率的に解くことができます。

1. L ^ R の値を計算する
2. その値の最上位ビット(MSB)の位置を求める
3. MSBの位置から下位に向かってすべてのビットを1にした値が答えになる

なぜこの方法で正しいのか

L ^ R の最上位ビットが立っているということは、その桁において L と R の値が異なることを意味します。つまり、その桁では範囲内に「0」と「1」の両方が存在します。したがって、MSBの位置から下のすべてのビットについて、片方の数では0、もう片方の数では1となるような2つの整数を範囲内から必ず選ぶことができ、結果としてすべてのビットが1になった値(最大XOR)が得られます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int getMaxXOR(int L, int R){
    // L と R のXORを計算
    int LXR = L ^ R;
    int msbPos = 0;
    
    // 最上位ビットの位置を求める
    while (LXR) {
        msbPos++;
        LXR >>= 1;
    }
    
    // MSBの位置から下のビットをすべて1にする
    int maxXOR = 0;
    int two = 1;
    while (msbPos--) {
        maxXOR += two;
        two <<= 1;
    }
    return maxXOR;
}

int main(){
    int L = 1;
    int R = 21;
    cout << "Result = " << getMaxXOR(L, R) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Result = 31

計算量

このアルゴリズムの時間計算量は O(log R) であり、範囲内の全ペアを調べる O((R-L)^2) の総当たり法と比べて非常に高速です。特に R が大きい場合に有効な手法といえます。