C++에서 N 이진 문자열의 비트 AND

<시간/>

이 문제에서는 크기가 n인 이진 문자열의 배열 bin[]이 제공됩니다. 우리의 임무는 N 바이너리 문자열의 비트 AND(&)를 찾는 프로그램을 만드는 것입니다.

여기서 우리는 모든 숫자를 가져와서 비트 AND를 찾습니다. 즉, bin[0] &bin[1] &... bin[n-2] &bin[n]

문제를 이해하기 위해 예를 들어보겠습니다.

입력 -

bin[] = {“1001”, “11001”, “010101”}

출력 -

설명 − 모든 이진 문자열의 비트 AND −

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

이 문제를 해결하기 위해 직접적이고 간단한 접근 방식은 두 이진 문자열의 비트 AND를 찾은 다음 다음 결과의 비트 AND를 찾아 배열의 마지막 문자열까지 계속하는 것입니다.

기본 알고리즘은 다음과 같습니다.

처음에 → 결과 =bin[0] 및 i =1

1단계 − 배열이 끝날 때까지 2단계와 3단계를 반복합니다.

2단계 - 결과 =결과 및 빈[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;
   }
}

출력

이 방법은 쉽지만 문자열을 통과해야 하므로 가장 효과적인 방법은 아닙니다.

보다 효과적인 솔루션에 대해 논의해 보겠습니다.

여기에서 이진수의 가장 작은 비트와 가장 큰 비트의 크기를 찾습니다. 그런 다음 숫자의 각 비트에 대한 비트 AND를 찾고 마지막에 선행 0을 추가합니다(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;
}