Trong bài toán này, chúng ta được cung cấp một bin mảng [] kích thước n của các chuỗi nhị phân. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Bitwise AND (&) của N chuỗi nhị phân.
Ở đây, chúng tôi sẽ lấy tất cả các số và tìm theo chiều kim loại VÀ trong số đó, tức là bin [0] &bin [1] &... bin [n-2] &bin [n]
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào -
bin[] = {“1001”, “11001”, “010101”} Đầu ra -
000001
Giải thích - Bitwise AND của tất cả chuỗi nhị phân -
(1001) & (11001) & (010101) = 000001
Để giải quyết vấn đề này, một cách tiếp cận trực tiếp và đơn giản là tìm AND theo chiều dọc của hai chuỗi nhị phân và sau đó tìm AND theo chiều bit của kết quả với chuỗi tiếp theo và tiếp tục cho đến chuỗi cuối cùng của mảng.
Thuật toán cơ bản sẽ là -
ban đầu → result =bin [0] và i =1
Bước 1 - Lặp lại bước 2 và 3 cho đến khi mảng kết thúc.
Bước 2 - result =result &bin [i]
Bước 3 - i ++;
Bước 4 - in kết quả.
Bây giờ, hãy giải quyết ví dụ với sự trợ giúp của phương pháp này -
bin[] = {“1001”, “11001”, “010101”}
result = bin[0] = 1001, i = 1 Lặp lại 1 -
result = 1001 & 11001 = 01001 i = 2
Lặp lại 2 -
result = 01001 & 010101 = 000001 i = 3. END
Ví dụ
Chương trình minh họa giải pháp trên,
#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;
}
} Đầu ra
000001
Cách tiếp cận này dễ dàng nhưng không phải là cách hiệu quả nhất vì nó cần phải duyệt qua chuỗi.
Hãy thảo luận về một giải pháp hiệu quả hơn,
Ở đây, chúng ta sẽ tìm kích thước của các bit nhỏ nhất và lớn nhất của số nhị phân. Sau đó, chúng tôi sẽ tìm theo từng bit VÀ của mỗi bit của số và ở cuối chúng tôi sẽ thêm các số 0 vào trước (số của số không sẽ là lớn nhất - nhỏ nhất).
Hãy lấy một ví dụ mẫu để làm rõ giải pháp,
bin[] = {"1001", "11001", "010101"}
Largest = 010101 smallest = 1001
010101 & 1001 = 00001 Ví dụ
Chương trình cho thấy việc thực hiện phương pháp trên -
#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;
} Đầu ra
000001