LeetCode 67. 二進制求和：字符串模擬加法 C 語言解法詳解

LeetCode 67. 二進制求和：字符串模擬加法 C 語言解法詳解

給定兩個二進制字符串，返回它們的和（也是二進制字符串）。本文提供從右向左逐位相加、處理進位、最後反轉字符串的完整 C 語言實現，並分析邊界情況與優化技巧。

算法思路：模擬豎式二進制加法

1. 雙指針 `i`、`j` 分別指向兩字符串末尾（最低位）。
2. 變量 `carry` 存儲進位（0 或 1）。
3. 循環條件：`i >= 0 || j >= 0 || carry == 1`。
4. 每輪取當前位數值（`a[i]-'0'`），相加得 `sum`。
5. 當前結果位 = `sum % 2`，存入臨時緩衝區；`carry = sum / 2`。
6. 循環結束後，緩衝區內為逆序結果，需反轉。
7. 添加 `\0` 結尾，返回字符串。

完整 C 語言實現

char* addBinary(char* a, char* b) {
    int i = strlen(a) - 1;
    int j = strlen(b) - 1;
    int carry = 0;
    // 最大可能長度 = max(len_a, len_b) + 1 (進位) + 1 (\0)
    int max_len = (i > j ? i : j) + 3;
    char *result = (char*)malloc(max_len);
    char *p = result; // 寫指針

    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        *p++ = (sum % 2) + '0'; // 存入低位
        carry = sum / 2;
    }
    *p = '\0';

    // 反轉字符串
    int len = p - result;
    for (int l = 0, r = len - 1; l < r; l++, r--) {
        char tmp = result[l];
        result[l] = result[r];
        result[r] = tmp;
    }
    return result;
}

關鍵點解析

• 字符轉數值：`'0'` ASCII 碼 48，`'1'` 49，`ch - '0'` 得 0/1。
• 緩衝區大小：`max(len_a, len_b) + 2` 足夠（+1 進位 +1 結尾符），代碼中 `+3` 更保險。
• 循環條件：`carry` 納入條件，自動處理最高位進位（如 "1" + "1" = "10"）。
• 反轉必要性：從低位向高位計算，結果自然逆序，必須反轉。
• 內存責任：返回 `malloc` 內存，**調用者必須 `free`**。

複雜度分析

• 時間：O(max(m, n))，單次遍歷 + 反轉。
• 空間：O(max(m, n))，結果字符串空間。

測試用例

a = "11", b = "1"    → "100"
a = "1010", b = "1011" → "10101"
a = "0", b = "0"     → "0"
a = "1111", b = "1111" → "11110"

總結

二進制字符串加法本質是基數為 2 的多精度加法。關鍵在於：正確處理字符與數值轉換、循環條件包含進位、結果反轉、內存管理。此模板可直接擴展至任意進制字符串加法（修改基數常量即可）。