LeetCode Add Binary：字符串二進制加法模擬

LeetCode 67 Add Binary - 二進制字符串相加

給定兩個二進制字符串 a, b，返回它們和的二進制字符串。長度可不等。

模擬逐位相加

• 從最低位（字符串末尾）向高位遍歷
• 維護進位 carry
• 每位：sum = (a_bit + b_bit + carry)，結果位 sum % 2，新進位 sum / 2
• 結果反轉輸出（因從低位向高位生成）

Java 實現

public String addBinary(String a, String b) {
    if (a.isEmpty()) return b;
    if (b.isEmpty()) return a;
    StringBuilder res = new StringBuilder();
    int i = a.length()-1, j = b.length()-1, carry = 0;
    while (i>=0 || j>=0) {
        int sum = carry;
        if (i>=0) sum += a.charAt(i--) - '0';
        if (j>=0) sum += b.charAt(j--) - '0';
        res.append(sum & 1);
        carry = sum >> 1;
    }
    if (carry > 0) res.append(carry);
    return res.reverse().toString();
}

關鍵點

• 用 StringBuilder 高效拼接字符
• sum & 1 取模 2，sum >> 1 除以 2，位運算更快
• 循環條件 i>=0 || j>=0 處理長度不同
• 別忘記最後進位
• 時間 O(max(|a|,|b|))，空間 O(max(|a|,|b|))

C++ 版本

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