C++で指定範囲内の最大ビットANDペアを求める方法

問題の概要

範囲 [L, R] が与えられたとき、L ≤ X < Y ≤ R を満たす整数のペア (X, Y) の中から、ビットごとのAND（論理積）である X & Y が最大になる組み合わせを見つけ、その値を出力するのが課題です。

具体例

L = 1、R = 10 の場合を考えてみましょう。このとき最大のビットAND値は 8 となり、次のように求められます。

1000   # 8 の2進数表現
& 1001   # 9 の2進数表現
----
1000   # 最終結果 = 8

アプローチ

最もシンプルな方法は、L から R までのすべての数値ペアを総当たりで調べることです。各ペアに対してビットAND演算を実行し、その結果の中から最大値を記録していきます。すべてのペアを確認し終えた時点で保持されている最大値が答えとなります。

C++での実装例

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

int getMaxBitwiseAndValue(int L, int R) {
    int maxValue = L & R;
    for (int i = L; i < R; ++i) {
        for (int j = i + 1; j <= R; ++j) {
            maxValue = max(maxValue, (i & j));
        }
    }
    return maxValue;
}

int main() {
    int L = 1, R = 10;
    cout << "Maximum value = " << getMaxBitwiseAndValue(L, R) << endl;
    return 0;
}

実行結果

Maximum value = 8

補足：計算量について

この総当たり方式は二重ループを使用するため、時間計算量は O((R−L)²) となります。初期値として L & R を設定しておくことで、わずかな効率化も図っています。範囲が狭い場合は十分実用的ですが、範囲が広くなると処理時間が急激に増加します。そのため、大きな範囲を扱うケースでは、ビット演算の性質（共通プレフィックスや2のべき乗の境界など）を活用したより効率的なアルゴリズムを検討するとよいでしょう。