C++で配列の全サブセットのAND値の最小値を求める方法

問題の概要

整数の配列が与えられたとき、その配列から取り出せるすべてのサブセット（部分集合）について要素全体のAND（ビットごとの論理積）を計算し、その中で最小となるAND値を求めて出力するのが課題です。

例

配列 arr[] = {1, 2, 3, 4, 5} の場合、2要素からなるサブセットのAND値は次のようになります。

(1 & 2) = 0
(1 & 3) = 1
(1 & 4) = 0
(1 & 5) = 1
(2 & 3) = 2
(2 & 4) = 0
(2 & 5) = 0
(3 & 4) = 0
(3 & 5) = 1
(4 & 5) = 4

解法のポイント

すべてのサブセットを列挙してAND値を計算するのは非常に非効率です。ここでAND演算の重要な性質に注目しましょう。

• AND演算では、ビットが「1」から「0」に変わることはあっても、「0」から「1」に変わることはありません。
• つまり、サブセットに要素を追加するたびに、AND値は減るか同じ値のままとなり、決して増えることはありません。
• したがって、配列の全要素を含むサブセット（配列全体）のAND値こそが、すべてのサブセットの中で最小のAND値になります。

この性質より、答えは単純に「配列の全要素のAND」となり、配列を一度走査するだけで求められます。

C++での実装例

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

int getMinAndValue(int *arr, int n) {
    int result = arr[0];
    for (int i = 1; i < n; ++i) {
        result = result & arr[i];
    }
    return result;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum value = " << getMinAndValue(arr, n) << endl;
    return 0;
}

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

出力

Minimum value = 0

計算量

• 時間計算量: O(n) — 配列の各要素を1回ずつ処理するだけです。
• 空間計算量: O(1) — 追加のメモリは不要です。

まとめ

AND演算の単調性（要素を増やしてもAND値が増えることはない性質）を利用することで、サブセットを全列挙することなく、配列全体のAND値を1回の走査で計算するだけで最小値が求められることが分かりました。シンプルでありながら、ビット演算の性質を活かした効率的な解法と言えます。