Chương trình cộng hai chuỗi nhị phân trong C++

Cho hai chuỗi biểu diễn số nhị phân, nhiệm vụ là cộng chúng và trả về kết quả dưới dạng chuỗi nhị phân.

Số nhị phân chỉ gồm 0 và 1. Quy tắc cộng nhị phân:

0+0 → 0
0+1 → 1
1+0 → 1
1+1 → 0, nhớ 1

Đầu vào 1

str1 = "11", str2 = "1"

Đầu ra 1

"100"

Đầu vào 2

str1 = "110", str2 = "1"

Đầu ra 2

"111"

Phương pháp tiếp cận

• Duyệt cả hai chuỗi từ cuối (bit thấp nhất)
• Cộng bit tương ứng, xử lý nhớ
• Xây dựng chuỗi kết quả

Thuật toán

string congNhiPhan(string a, string b) {
    string ketQua = "";
    int nho = 0;
    int i = a.size() - 1;
    int j = b.size() - 1;
    
    while (i >= 0 || j >= 0 || nho == 1) {
        nho += (i >= 0) ? a[i] - '0' : 0;
        nho += (j >= 0) ? b[j] - '0' : 0;
        ketQua = char(nho % 2 + '0') + ketQua;
        nho /= 2;
        i--; j--;
    }
    return ketQua;
}

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

string congNhiPhan(string a, string b) {
    string ketQua = "";
    int nho = 0;
    int i = a.size() - 1;
    int j = b.size() - 1;
    while (i >= 0 || j >= 0 || nho == 1) {
        nho += (i >= 0) ? a[i] - '0' : 0;
        nho += (j >= 0) ? b[j] - '0' : 0;
        ketQua = char(nho % 2 + '0') + ketQua;
        nho /= 2;
        i--; j--;
    }
    return ketQua;
}

int main() {
    string a = "10101", b = "11100";
    cout << "Tổng hai chuỗi nhị phân: " << congNhiPhan(a, b);
    return 0;
}

Kết quả chạy chương trình

Tổng hai chuỗi nhị phân: 110001