C++で配列内のペアから得られる最大のビット単位AND（論理積）値を求めるアルゴリズム

問題文

n個の正の整数からなる配列が与えられます。この中から任意の2つの要素を選んだペアについて、ビット単位AND（論理積）の最大値を求めるのが本問題です。

例

入力配列が {10, 12, 15, 18} の場合、ビット単位ANDの最大値は 12 となります。これは 12 (1100) と 15 (1111) のANDを取った結果 1100（= 12）が最も大きいためです。

アルゴリズム

ビット単位ANDでは、両方のビットが1である場合にのみ、結果のその桁が1になります。この性質を利用すると、以下のような貪欲法で効率よく最適解を求められます。

• 最上位ビット（MSB）から順に、そのビットが立っている要素が配列内に2つ以上存在するかどうかを確認します。
• 2つ以上存在する場合は、そのビットは解の一部となるため結果に加算します。存在しない場合は、そのビットを破棄します。
• 同様に、MSBからLSBへ（32ビット目から1ビット目まで）各ビット位置を順番に調べていくことで、解に含まれるべきビットを特定し、それらすべてを結果に足し合わせていきます。

この手法では、各ビットについて配列全体を一度走査するだけなので、計算量は O(32 × n)、つまり実質 O(n) で済み、全ペアを総当たりする O(n²) よりもはるかに高速です。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int checkBits(int *arr, int n, int pattern) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if ((pattern & arr[i]) == pattern) {
            ++cnt;
        }
    }
    return cnt;
}
int getMaxBitwiseAnd(int *arr, int n) {
    int result = 0;
    int count;
    for (int i = 31; i >= 0; --i) {
        count = checkBits(arr, n, result | (1 << i));
        if (count >= 2) {
            result |= (1 << i);
        }
    }
    return result;
}
int main() {
    int arr[] = {10, 12, 15, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum bitwise AND = " << getMaxBitwiseAnd(arr, n) << endl;
    return 0;
}

コードのポイント

• checkBits 関数は、指定したパターンのビットがすべて立っている要素の個数を数えます。(pattern & arr[i]) == pattern という条件で、パターンに含まれる全ビットが対象の要素でも立っていることを確認できます。
• getMaxBitwiseAnd 関数では、すでに確定した結果に対して新しい候補ビットをORで追加した値を使って判定することで、これまで確定したビットとの整合性を保ちながら処理を進めています。

出力

Maximum bitwise AND = 12