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 - परिणाम = परिणाम & bin[i]

चरण 3 - i++;

चरण 4 - परिणाम प्रिंट करें।

अब, आइए इस दृष्टिकोण की मदद से उदाहरण हल करें -

bin[] = {"1001", "11001", "010101"} परिणाम = bin[0] = 1001, i = 1

पुनरावृत्ति 1 -

परिणाम = 1001 & 11001 = 01001 i = 2

पुनरावृत्ति 2 -

परिणाम = 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;
    }
}

आउटपुट

यह दृष्टिकोण आसान है लेकिन सबसे प्रभावी नहीं है क्योंकि इसे स्ट्रिंग को पार करने की आवश्यकता होती है।

आइए एक अधिक प्रभावी समाधान पर चर्चा करें,

यहां, हम बाइनरी संख्या के सबसे छोटे और सबसे बड़े बिट्स का आकार ढूंढेंगे। फिर हम संख्या के प्रत्येक बिट का बिटवाइज 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;
}