C++で少なくとも1つの非空部分配列のビット単位ANDとなる数値をすべて求める方法

本記事では、「与えられた配列に対して、少なくとも1つの非空（空でない）部分配列のビット単位ANDとして表現できるすべての整数を求める」という問題を解説します。具体的な入出力の例は以下の通りです。

入力：nums[ ] = { 3, 5, 1, 2, 8 }
出力：{ 2, 5, 0, 3, 8, 1 }
説明：
2 は部分配列 {2} のビット単位AND,
5 は部分配列 {5} のビット単位AND,
0 は部分配列 {1, 2}、{2, 8}、{1, 2, 8} のビット単位AND,
3 は部分配列 {3} のビット単位AND,
8 は部分配列 {8} のビット単位AND,
1 は部分配列 {1}、{3, 5}、{3, 5, 1} のビット単位AND。

入力：nums[ ] = { 2, 6, 3, 8, 1 }
出力：{ 1, 8, 3, 6, 2, 0 }

解決策へのアプローチ

まず、最もシンプルなアプローチとして以下の手順が考えられます。

• 考えられるすべての非空の部分配列を列挙する。

• 配列を走査しながら、各部分配列に含まれる要素同士のビット単位ANDを順次計算する。

• 重複した値を避けるため、すべての結果をセット（unordered_set）に格納する。

この手法の時間計算量はO(n²)であり、部分配列の総数に比例して処理が行われます。また、結果の格納には最大でO(n)程度のメモリを使用します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] ={ 2, 6, 3, 8, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // 各AND演算の結果を格納するためのセットを宣言
    unordered_set<int> result;
    int val;
    // すべての可能な非空部分配列を走査するためのネストされたループ
    for (int i = 0; i < n; ++i){
        for (int j = i, val = INT_MAX; j < n; ++j){
            val = val & arr[j];
            // AND演算の結果を保存
            result.insert(val);
        }
    }
    cout << "All possible numbers are: ";
    // セット内のすべての値を出力
    for (auto i = result.begin(); i != result.end();i++)
        cout << *i << " ";
    return 0;
}

出力結果

All possible numbers are: 1 8 3 6 0 2

コードの解説

• AND演算の結果をすべて格納するためのセットを宣言します。unordered_set を使うことで重複が自動的に排除されます。

• 変数「val」を INT_MAX で初期化しています。これは、すべてのビットが1の状態からAND演算を開始する必要があるためです（任意の数値とのANDで元の値が保持される）。

• 外側のループで開始位置 i を固定し、内側のループで i 番目のインデックス以降に存在するすべての部分配列を走査します。

• 各要素同士、および自分自身とのAND演算を累積的に計算し、その結果を result セットに挿入していきます。

• 最後に、result セット内のすべての値を出力して完了です。

まとめ

本記事では、この問題を解くためのシンプルなアプローチ、すなわちすべての可能な部分配列に対してビット単位ANDを計算する方法について解説しました。あわせて、この問題を解くC++プログラムの実装例も紹介しています。このロジックは、Java、C、Pythonなどの他のプログラミング言語でも同様に実装できます。本チュートリアルが皆様の学習のお役に立てば幸いです。