Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Bitwise AND của N xâu nhị phân trong C++

Trong bài toán này, ta được cho mảng bin[] kích thước n chứa xâu nhị phân. Nhiệm vụ: tạo chương trình tìm Bitwise AND (&) của N xâu nhị phân.

Ta lấy tất cả số và tìm bitwise AND: bin[0] & bin[1] & ... & bin[n-1].

Ví dụ minh họa

Đầu vào** –

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

Đầu ra** –

000001

Giải thích** – Bitwise AND của tất cả xâu nhị phân:

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

Cách trực tiếp: tính AND hai xâu, rồi AND kết quả với xâu tiếp theo, lặp đến cuối.

Thuật toán cơ bản:**

Khởi tạo: result = bin[0], i = 1

Bước 1** – Lặp Bước 2,3 đến hết mảng.

Bước 2** – result = result & bin[i]

Bước 3** – i++

Bước 4** – In result.

Ví dụ

Chương trình minh họa:

#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 này dễ nhưng chưa tối ưu do duyệt xâu nhiều lần.

Cách hiệu quả hơn: tìm độ dài nhỏ nhất và lớn nhất. Tính AND từng bit cho đến độ dài nhỏ nhất, sau đó thêm số 0 đầu bằng chênh lệch độ dài.

Ví dụ

Chương trình triển khai:

#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