C++でN個のバイナリ文字列のビット単位OR（論理和）を計算する方法

問題の概要

この問題では、n 個のバイナリ文字列からなる配列 bin[] が与えられます。私たちの課題は、これら n 個のバイナリ文字列すべてのビット単位OR（論理和）を求めるプログラムを作成することです。

具体的には、すべての文字列に対して次のような演算を行います。

bin[0] | bin[1] | ... | bin[n-2] | bin[n-1]

それでは、具体例を使って問題を理解しましょう。

入力：

bin[] = {"1001", "11001", "010101"}

出力：

011101

説明： すべてのバイナリ文字列のビット単位ORは以下のように計算されます。

(1001) | (11001) | (010101) = 011101

解決策のアプローチ

この問題を解くための手順はシンプルです。まず、最もビット数が多い（最長の）文字列を見つけます。次に、他のすべての文字列の先頭に必要な数だけ「0」を追加して長さを揃えます。その後、各桁ごとにビット単位ORを計算すれば結果が得られます。

アルゴリズムの動作を例で確認してみましょう。

bin[] = {"1101", "011010", "00111"}

最長の文字列は長さ6の「011010」です。そこで、他の文字列の先頭に0を追加して長さを揃えます。

更新後の文字列：「001101」「011010」「000111」

すべての文字列のビット単位ORを求めると、次のようになります。

001101 | 011010 | 000111 = 011111

C++での実装例

上記の解決策の動作を示すプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
string bitwiseOR(string* bin, int n){
    string result;
    int max_size = INT_MIN;
    // 最長の文字列の長さを求め、各文字列を反転
    for (int i = 0; i < n; i++) {
        max_size = max(max_size, (int)bin[i].size());
        reverse(bin[i].begin(), bin[i].end());
    }
    // 長さを揃えるために末尾（元の先頭）に0を追加
    for (int i = 0; i < n; i++) {
        string s;
        for (int j = 0; j < max_size - bin[i].size(); j++) s += '0';
        bin[i] = bin[i] + s;
    }
    // 各桁ごとにビット単位ORを計算
    for (int i = 0; i < max_size; i++) {
        int insertBit = 0;
        for (int j = 0; j < n; j++)
            insertBit = insertBit | (bin[j][i] - '0');
        result += (insertBit + '0');
    }
    // 結果を元の順序に戻す
    reverse(result.begin(), result.end());
    return result;
}
int main() {
    string bin[] = { "1101", "011010", "00111" };
    int n = sizeof(bin) / sizeof(bin[0]);
    cout<<"配列内のすべてのバイナリ文字列のビット単位ORは "<<bitwiseOR(bin, n);
    return 0;
}

コードのポイント

• 文字列を反転してから処理することで、桁の位置合わせが容易になります。
• 短い文字列には先頭（反転後は末尾）に「0」を補完し、すべての文字列の長さを最大長に揃えています。
• 各桁に対して全文字列のビットをOR演算し、その結果を連結して最終的な答えを構築します。

実行結果

配列内のすべてのバイナリ文字列のビット単位ORは 011111

まとめ

このように、長さの異なる複数のバイナリ文字列のビット単位ORを求める場合は、まず最長の文字列に合わせて先頭を0で埋めて長さを揃えることが重要なポイントです。この手法により、任意の個数・任意の長さのバイナリ文字列に対して効率的にOR演算を実行できます。時間計算量は O(n × L)（n は文字列の個数、L は最大長）となり、非常に効率的です。