解題說明
Add Binary
題目描述：給定兩個二進位字串 a 和 b，回傳它們相加的結果（同樣以二進位字串表示）。字串不含前導零（除非本身就是 "0"）。
解題思路：模擬手動二進位加法的過程，從最低位（字串末尾）開始向左逐位相加，並處理進位（carry）。
- 使用兩個指標
i、j分別指向a和b的末尾。 - 初始化進位
carry = 0。 - 當
i >= 0、j >= 0或carry != 0時持續迴圈：- 累加當前位的數字（若指標已超出範圍則視為 0）與
carry。 - 當前結果位 =
sum % 2，更新carry = sum / 2。 - 將結果位插入結果字串最前方。
- 累加當前位的數字（若指標已超出範圍則視為 0）與
- 由於我們是從低位往高位建構結果，最後反轉字串（或使用字串前插）即可。
使用 result 字串在尾端 append 再反轉，比每次前插（O(n) 操作）更有效率。
C++ 解法
複雜度分析
時間複雜度：O(max(m, n)) — m 和 n 分別為字串 a 和 b 的長度。迴圈執行次數等於較長字串的長度加上可能的最後進位，為線性時間。reverse 同樣為 O(max(m, n))。
空間複雜度：O(max(m, n)) — 結果字串的長度最多為 max(m, n) + 1（最高位可能產生進位）。
虛擬碼
1. Set i = a.size() - 1, j = b.size() - 1, carry = 0, result = "". 2. While i >= 0 OR j >= 0 OR carry != 0: a. sum = carry. b. If i >= 0: sum += a[i] - '0'; decrement i. c. If j >= 0: sum += b[j] - '0'; decrement j. d. Append (sum % 2) as a character to result. e. carry = sum / 2. 3. Reverse result. 4. Return result.
其他解法
內建大整數轉換 O(m+n)：在支援大整數的語言（如 Python）中，可直接用 int(a, 2) + int(b, 2) 轉換為整數相加，再用 bin() 轉回二進位字串。C++ 中因整數有位元上限，此法不適用於超長字串。
逐位 XOR + 進位模擬（位元操作風格）O(m+n)：本質與上述方法相同，但可以用 XOR 計算當前位（無進位加法），用 AND 後左移計算進位。在硬體描述語言（HDL）設計中這種加法器風格更常見，但在軟體層面並無效能優勢。
延伸思考
- 如果要實作「兩個十六進位字串相加」，程式碼需要做哪些修改？
- 若輸入字串非常長（例如長度 10^5），有什麼方式可以避免字串反轉帶來的額外開銷？
- 這道題本質上是模擬一個 1-bit 全加器（Full Adder）。如果要設計一個 n-bit 的漣波進位加法器（Ripple Carry Adder），你會如何用程式碼表達？