Bitwise และ N สตริงไบนารีใน C ++

ในปัญหานี้ เราได้รับอาร์เรย์ bin[] ขนาด n ของสตริงไบนารี งานของเราคือสร้างโปรแกรมเพื่อค้นหา Bitwise และ (&) ของสตริงไบนารี N

ที่นี่ เราจะนำตัวเลขทั้งหมดมาและหาค่าระดับบิต AND ของตัวเลขเหล่านั้น เช่น bin[0] &bin[1] &... bin[n-2] &bin[n]

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล −

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

ผลผลิต −

คำอธิบาย − Bitwise AND ของสตริงไบนารีทั้งหมด -

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

ในการแก้ปัญหานี้ วิธีการโดยตรงและง่าย ๆ คือการค้นหาค่าบิต 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;
   }
}

ผลลัพธ์

วิธีนี้ง่ายแต่ไม่ได้ผลมากที่สุดเพราะต้องข้ามผ่านสตริง

มาคุยกันถึงวิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้น

ที่นี่ เราจะพบขนาดของบิตที่เล็กที่สุดและใหญ่ที่สุดของเลขฐานสอง จากนั้นเราจะหาค่าระดับบิต 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;
}