Cách cộng n chuỗi nhị phân trong C++?

Chúng ta sẽ xem cách viết chương trình có thể cộng n số nhị phân được cho dưới dạng chuỗi. Cách dễ dàng nhất là chuyển đổi chuỗi nhị phân sang dạng thập phân tương đương, cộng chúng lại, rồi chuyển đổi ngược lại thành nhị phân. Ở đây chúng ta sẽ thực hiện phép cộng thủ công.

Chúng ta sẽ sử dụng một hàm hỗ trợ để cộng hai chuỗi nhị phân. Hàm này sẽ được gọi n-1 lần cho n chuỗi nhị phân khác nhau. Hàm hoạt động như sau:

Thuật toán

addTwoBinary(bin1, bin2)

bắt đầu
  s := 0
  result là chuỗi rỗng
  i := độ dài của bin1, và j := độ dài của bin2
  while i >= 0 HOẶC j >= 0 HOẶC s là 1, thực hiện
    nếu i >= 0 thì
      s := s + bin1[i] dưới dạng số
    ngược lại
      s := s + 0
    kết thúc nếu
    nếu j >= 0 thì
      s := s + bin2[j] dưới dạng số
    ngược lại
      s := s + 0
    kết thúc nếu
    result := (s mod 2) nối với result
    s := s / 2
    i := i - 1
    j := j - 1
  done
  trả về result
kết thúc

Ví dụ

#include <iostream>
using namespace std;

string addTwoBinary(string bin1, string bin2) {
  string result = "";
  int s = 0; // s dùng để lưu tổng bit
  int i = bin1.length() - 1, j = bin2.length() - 1; // duyệt từ LSB
  while (i >= 0 || j >= 0 || s == 1) {
    if(i >= 0)
      s += bin1[i] - '0';
    else
      s += 0;
    if(j >= 0)
      s += bin2[j] - '0';
    else
      s += 0;
    result = char(s % 2 + '0') + result;
    s /= 2; // lấy carry
    i--; j--;
  }
  return result;
}

string add_n_binary(string arr[], int n) {
  string result = "";
  for (int i = 0; i < n; i++)
    result = addTwoBinary(result, arr[i]);
  return result;
}

int main() {
  string arr[] = { "1011", "10", "1001" };
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << add_n_binary(arr, n) << endl;
  return 0;
}

Kết quả

10110