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を見つけて、配列の最後の文字列まで続けることです。

基本的なアルゴリズムは-になります

最初は →結果=bin[0]およびi=1

ステップ1 −アレイが終了するまで、手順2と3を繰り返します。

ステップ2 −結果=結果と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. END

例

上記の解決策を説明するプログラム

#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

このアプローチは簡単ですが、文字列をトラバースする必要があるため、最も効果的なアプローチではありません。

より効果的な解決策について話し合いましょう

ここでは、2進数の最小ビットと最大ビットのサイズを確認します。次に、数値の各ビットのビットごとのANDを見つけ、最後に先行する0を追加します（ゼロの数が最大-最小になります）。

解決策を明確にするためのサンプル例を見てみましょう。

bin[] = {"1001", "11001", "010101"}
Largest = 010101 smallest = 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