C++でN個のバイナリ文字列のビットごとのAND（論理積）を計算する方法

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

具体的には、すべての数値に対してビットごとのANDを適用します。つまり、bin[0] & bin[1] & ... & bin[n-2] & bin[n] のような形で計算を行います。

問題を理解するための具体例

入力：

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

出力：

000001

説明： すべてのバイナリ文字列に対してビットごとのANDを適用すると、以下の結果が得られます。

(1001) & (11001) & (010101) = 000001

シンプルなアプローチ

この問題を解く最も直接的で簡単な方法は、まず2つのバイナリ文字列のビットごとのANDを計算し、その結果と次の文字列のANDを求めるという操作を、配列の末尾に達するまで順番に繰り返すことです。

基本的なアルゴリズム

初期状態： result = bin[0]、i = 1

• ステップ1： 配列の終わりまでステップ2とステップ3を繰り返します。
• ステップ2： result = result & bin[i]
• ステップ3： i++ （インデックスを進める）
• ステップ4： 結果を出力します。

それでは、このアプローチを使って先ほどの例を実際に解いてみましょう。

bin[] = {"1001", "11001", "010101"}
result = bin[0] = 1001, i = 1

反復1：

result = 1001 & 11001 = 01001
i = 2

反復2：

result = 01001 & 010101 = 000001
i = 3. 終了

実装コード例

上記の解法を実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;
int changeLength(string &a, string &b){
    int lengtha = a.length();
    int lengthb = b.length();
    int zeros = abs(lengtha-lengthb);
    if (lengtha<lengthb) {
        for (int i = 0 ; i<zeros; i++)
        a = '0' + a;
        return lengthb;
    }
    else {
        for (int i = 0 ; i<zeros; i++)
        b = '0' + b;
    }
    return lengtha;
}
string bitwiseAND(string binary1, string binary2){
    int length = changeLength(binary1,binary2);
    string result = "";
    for (int i = 0 ; i<length; i++){
        result = result+(char)((binary1[i] - '0' & binary2[i]-'0')+'0');
    }
    return result;
}
int main(){
    string bin[] = {"1001", "11001", "010101"};
    int n = sizeof(bin)/sizeof(bin[0]);
    string result;
    if (n<2){
        cout<<bin[n-1]<<endl;
    }
    else{
        result = bin[0];
        for (int i = 1; i<n; i++)
        result = bitwiseAND(result, bin[i]);
        cout <<result<<endl;
    }
}

出力

000001

このアプローチは理解しやすい反面、各文字列を先頭から走査する必要があるため、必ずしも最も効率的な方法とは言えません。

より効率的なアプローチ

続いて、より効率的な解決策について見ていきましょう。

この方法では、まず与えられたバイナリ数の中から最小の桁数と最大の桁数を特定します。その後、共通する下位の桁部分について各ビットごとのANDを計算し、最後に先頭へ0を補填します（追加する0の数は「最大桁数 − 最小桁数」に相当します）。これは、短い方のバイナリ数の上位桁には必ず暗黙的な0が並んでいるため、その位置のAND結果は必然的に0になるという性質を利用しています。

サンプル例を使って、この解法を分かりやすく確認してみましょう。

bin[] = {"1001", "11001", "010101"}
最大桁数の文字列 = 010101、最小桁数の文字列 = 1001
010101 & 1001 = 00001

実装コード例

上記の効率的なアプローチを実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
string bitwiseANDarray(string* bin, int n){
    string result;
    int minSize = INT_MAX;
    int maxSize = INT_MIN;
    for (int i = 0; i < n; i++) {
        reverse(bin[i].begin(), bin[i].end());
        minSize = min(minSize, (int)bin[i].size());
        maxSize = max(maxSize, (int)bin[i].size());
    }
    for (int i = 0; i < minSize; i++) {
        bool setBit = true;
        for (int j = 0; j < n; j++) {
            if (bin[j][i] == '0') {
                setBit = false;
                break;
            }
        }
        result += (setBit ? '1' : '0');
    }
    for (int i = 0; i<abs(maxSize-minSize); i++)
    result += '0';
    reverse(result.begin(), result.end());
    return result;
}
int main(){
    string arr[] = {"1001", "11001", "010101"};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<bitwiseANDarray(arr, n);
    return 0;
}

出力

000001

このように、文字列を反転させて下位桁から比較することで、余分な走査を減らしながら効率よくビットごとのANDを計算できます。データ量が多い場合や文字列の長さに大きな差がある場合には、後者のアプローチの方が優れたパフォーマンスを発揮します。