LeetCode 67. Add Binary：二進制字串相加的高效實現與優化技巧

題目描述

給定兩個二進制字串 a、b，回傳它們相加後的二進制字串。輸入非空、僅含 '0'/'1'、無前導零（除 "0" 本身）。

核心思路：模擬列竪式加法

從最低位（字串末尾）向最高位遍歷，維護進位 carry，逐位計算：

sum = (a[i]-'0') + (b[j]-'0') + carry
resultBit = sum % 2
carry = sum / 2

原始代碼分析與問題

public String addBinary(String a, String b) {
    char[] aa = a.toCharArray(), bb = b.toCharArray();
    int size = Math.max(aa.length, bb.length);
    int[] mm = new int[size];
    int c = 0, i = aa.length-1, j = bb.length-1, k = size-1;
    // 同時遍歷兩字串
    for (; i>=0 && j>=0; i--, j--, k--) {
        mm[k] = (aa[i]-'0' + bb[j]-'0' + c) % 2;
        c = (aa[i]-'0' + bb[j]-'0' + c >= 2) ? 1 : 0;
    }
    // 處理剩餘長字串
    while (i >= 0) { mm[k] = (aa[i]-'0' + c) % 2; c = (aa[i]-'0' + c >= 2) ? 1 : 0; k--; i--; }
    while (j >= 0) { mm[k] = (bb[j]-'0' + c) % 2; c = (bb[j]-'0' + c >= 2) ? 1 : 0; k--; j--; }
    // 最高位進位
    String s = (c == 1) ? "1" : "";
    for (int n = 0; n < mm.length; n++) s += mm[n];
    return s;
}

問題：

• 重複計算 aa[i]-'0' 等表達式，可讀性差。
• 字串拼接 s += mm[n] 在循環中產生大量臨時對象，效率低（O(N²)）。
• 邊界條件處理分散在三個循環，邏輯冗餘。

優化版：StringBuilder + 統一循環

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

優化亮點

1. 單一循環：i>=0 || j>=0 || carry>0 統一處理所有情況，無需分段。
2. 位運算：sum & 1 替代 %2，sum >> 1 替代 /2，極快。
3. StringBuilder：O(N) 構建結果，最後 reverse() 得到正序。
4. charAt 直接取碼點：避免 toCharArray() 複製陣列。

return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);