67. Add Binary

Easy

Description

給定兩個二進位字串 a 和 b，回傳它們的和（也是二進位字串）。

Example:

Input: a = “1010”, b = “1011” Output: “10101”

Intuition#

核心思路：模擬二進位加法——從最低位開始逐位相加，處理進位。

與十進位加法相同的邏輯，只是基數從 10 變為 2
從兩個字串的末尾同時開始，逐位相加
每位的結果 = (a_bit + b_bit + carry) % 2，進位 = (a_bit + b_bit + carry) / 2

Approaches#

⭐1: 模擬二進位加法#

概念: 雙指標從末尾開始，逐位計算和與進位
時間複雜度: O(max(m, n)) - m, n 為兩字串長度
空間複雜度: O(max(m, n)) - 結果字串

class Solution {
    fun addBinary(a: String, b: String): String {
        val sb = StringBuilder()
        var i = a.length - 1
        var j = b.length - 1
        var carry = 0

        while (i >= 0 || j >= 0 || carry > 0) {
            var sum = carry
            if (i >= 0) {
                sum += a[i] - '0'
                i--
            }
            if (j >= 0) {
                sum += b[j] - '0'
                j--
            }
            sb.append(sum % 2)
            carry = sum / 2
        }

        return sb.reverse().toString()
    }
}

2: 位元操作（不用加法）#

概念: 用 XOR 做不進位加法，AND + 左移做進位計算，重複直到無進位。需用 BigInteger 處理大數
時間複雜度: O(max(m, n)) - 最多迭代 max(m,n) 次
空間複雜度: O(max(m, n))

import java.math.BigInteger

class Solution {
    fun addBinary(a: String, b: String): String {
        var x = BigInteger(a, 2)
        var y = BigInteger(b, 2)
        while (y != BigInteger.ZERO) {
            val sum = x.xor(y)           // 不進位加法
            val carry = x.and(y).shiftLeft(1)  // 進位
            x = sum
            y = carry
        }
        return x.toString(2)
    }
}

🔑 Takeaways#

Pattern: 大數加法模板——從低位到高位逐位處理，適用於任何進位制
關鍵技巧: sum % 2 取當前位、sum / 2 取進位；記得處理最後一個 carry