โปรแกรมบวกสตริงเลขฐานสอง (Binary Strings) ใน C++

ภาพรวมปัญหา

โปรแกรมนี้ใช้บวกสตริงเลขฐานสอง (Binary Strings) สองตัว และคืนค่าผลลัพธ์เป็นสตริงฐานสอง เช่นกัน โดยไม่แปลงเป็นตัวเลขฐานสิบ

กติกาการบวกเลขฐานสอง

ขั้นตอนการทำงาน

1. เริ่มจากบิตขวามือสุด (Least Significant Bit) ของทั้งสองสตริง
2. บวกบิตแต่ละคู่พร้อมกับ carry จากขั้นตอนก่อนหน้า
3. เก็บผลบวก (sum % 2) และอัปเดต carry (sum / 2)
4. เลื่อนไปทางซ้ายจนครบทุกบิตและไม่มี carry ค้าง
5. สร้างสตริงผลลัพธ์ (ต้องกลับลำดับเพราะคำนวณจากขวาไปซ้าย)

ตัวอย่างการคำนวณ

   10101  (21)
+  11100  (28)
--------
  110001  (49)

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

#include <iostream>
#include <string>
using namespace std;

string addBinaryStrings(string a, string b) {
    string result = "";
    int carry = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;
    
    while (i >= 0 || j >= 0 || carry == 1) {
        int sum = carry;
        if (i >= 0) sum += a[i] - '0';
        if (j >= 0) sum += b[j] - '0';
        
        result = char('0' + (sum % 2)) + result;
        carry = sum / 2;
        
        i--;
        j--;
    }
    
    return result;
}

int main() {
    string testCases[][2] = {
        {"11", "1"},
        {"110", "1"},
        {"10101", "11100"},
        {"1111", "1111"},
        {"0", "0"}
    };
    
    for (auto &tc : testCases) {
        cout << tc[0] << " + " << tc[1] << " = " << addBinaryStrings(tc[0], tc[1]) << endl;
    }
    return 0;
}

ผลลัพธ์ตัวอย่าง

11 + 1 = 100
110 + 1 = 111
10101 + 11100 = 110001
1111 + 1111 = 11110
0 + 0 = 0

ความซับซ้อนของอัลกอริทึม

• เวลา: O(max(m, n)) โดย m, n คือความยาวสตริง
• พื้นที่: O(max(m, n)) สำหรับเก็บผลลัพธ์

เทคนิคการเพิ่มประสิทธิภาพ

• ใช้ reserve() สำหรับ string เพื่อลดการจัดสรรหน่วยความจำซ้ำ
• ใช้ push_back() แล้ว reverse() ท้ายสุด แทนการต่อหน้าสตริง (ซึ่งเป็น O(n²))

โค้ดที่ปรับปรุงประสิทธิภาพ

string addBinaryOptimized(string a, string b) {
    string result;
    result.reserve(max(a.size(), b.size()) + 1);
    int carry = 0;
    int i = a.size() - 1, j = b.size() - 1;
    
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        result.push_back('0' + (sum & 1));
        carry = sum >> 1;
    }
    
    reverse(result.begin(), result.end());
    return result;
}

การใช้งานจริง

• การคำนวณเลขใหญ่ (Big Integer Arithmetic)
• การเข้ารหัสและการบีบอัดข้อมูล
• การจำลองวงจรดิจิทัล