二進位加法演算法：大整數字串相加實作

給定兩個最長 80 位元的二進位字串，求其和（最長 81 位元）。輸入最多 1000 組測資，需輸出測資編號與不含前導零的結果。

演算法思路

• 從右向左逐位相加，維護進位 carry。
• 位元相加規則：0+0=0, 1+0=1, 0+1=1, 1+1=0 進1, 1+1+1=1 進1。
• 使用 StringBuilder 反向建構結果，最後反轉並去除前導零。

Java 參考實作

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);
        carry = sum >> 1;
    }
    String res = sb.reverse().toString();
    return res.replaceFirst("^0+(?!$)", ""); // 去除前導零，保留至少一位
}

時間複雜度 O(max(lenA, lenB))，空間複雜度 O(max(lenA, lenB))，完全符合題目限制。