การบวกสตริงไบนารี n ตัวใน C++

ในบทความนี้เราจะดูวิธีเขียนโปรแกรมที่สามารถบวกเลขไบนารี n ตัวที่ให้มาในรูปแบบสตริง วิธีที่ง่ายที่สุดคือการแปลงสตริงไบนารีเป็นค่าเทียบเท่าทศนิยม แล้วบวกกันและแปลงกลับเป็นไบนารี แต่ที่นี่เราจะทำการบวกด้วยตนเอง

เราจะใช้ฟังก์ชันช่วย addTwoBinary เพื่อบวกสตริงไบนารีสองตัว ฟังก์ชันนี้จะถูกเรียกใช้ n-1 ครั้งสำหรับสตริงไบนารี n ตัว ฟังก์ชันทำงานดังนี้:

อัลกอริทึม

addTwoBinary(bin1, bin2)

เริ่มต้น  s := 0
result เป็นสตริงว่าง
i := ความยาวของ bin1, และ j := ความยาวของ bin2
while i >= 0 หรือ j >= 0 หรือ s เป็น 1 ทำ
  ถ้า i >= 0 แล้ว
    s := s + bin1[i] เป็นตัวเลข
  มิฉะนั้น
    s := s + 0
  จบถ้า
  ถ้า j >= 0 แล้ว
    s := s + bin2[j] เป็นตัวเลข
  มิฉะนั้น
    s := s + 0
  จบถ้า
  result := (s mod 2) ต่อหน้ากับ result เอง
  s := s / 2
  i := i - 1
  j := j - 1
จบ while
คืนค่า result
สิ้นสุด

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

string addTwoBinary(string bin1, string bin2) {
    string result = "";
    int s = 0; // s จะเก็บผลรวมของบิต
    int i = bin1.length() - 1, j = bin2.length() - 1; // เริ่มจาก 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; // ได้ค่า 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;
}

ผลลัพธ์

10110