Bitwise AND ของ N สตริงไบนารีใน C++

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

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

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต −

bin[] = {"1001", "11001", "010101"}

เอาต์พุต −

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

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

เพื่อแก้ปัญหานี้ วิธีตรงไปตรงมาและง่ายคือการหา bitwise AND ของสตริงไบนารี 2 ตัว แล้วหา bitwise AND ของผลลัพธ์กับตัวถัดไป และทำต่อไปจนถึงสตริงสุดท้ายของอาร์เรย์

อัลกอริทึมพื้นฐานจะเป็น −

เริ่มต้น → result = bin[0] และ i = 1

ขั้นตอน 1 − ทำซ้ำขั้นตอน 2 และ 3 จนกว่าอาร์เรย์จะจบ

ขั้นตอน 2 − result = result & bin[i]

ขั้นตอน 3 − i++

ขั้นตอน 4 − พิมพ์ผลลัพธ์

ตอนนี้ มาแก้ตัวอย่างด้วยวิธีนี้ −

bin[] = {"1001", "11001", "010101"} result = bin[0] = 1001, i = 1
Iteration 1 − result = 1001 & 11001 = 01001 i = 2
Iteration 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;
    }
}

เอาต์พุต

วิธีนี้ง่ายแต่ไม่ใช่ที่มีประสิทธิภาพที่สุด เพราะต้องเดินผ่านสตริงหลายครั้ง

วิธีที่มีประสิทธิภาพมากกว่า

ที่นี่ เราจะหาขนาดของบิตเล็กที่สุดและใหญ่ที่สุดของตัวเลขไบนารี แล้วหา bitwise AND ของแต่ละบิตของตัวเลข และท้ายสุดเพิ่ม 0 นำหน้า (จำนวน 0 จะเป็น largest - smallest)

ตัวอย่างการทำให้ชัดเจน −

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;
}