Intuition#

核心思路：XOR 算不進位的和，AND 左移一位算進位，重複直到進位為 0。

• 二進位加法的本質：每一位的和等於 XOR（不考慮進位），進位等於 AND 再左移一位
• 將「本位和」和「進位」反覆合併，直到進位為 0
• 這就是硬體加法器（Ripple Carry Adder）的運作原理

Approaches#

1: 迭代位元加法#

• 概念: 用 XOR 計算不進位的和，AND + 左移計算進位，重複直到無進位
• 時間複雜度: O(32) = O(1) - 最多 32 次迭代
• 空間複雜度: O(1)

class Solution {
    fun getSum(a: Int, b: Int): Int {
        var x = a
        var carry = b
        while (carry != 0) {
            val tmp = x xor carry
            carry = (x and carry) shl 1
            x = tmp
        }
        return x
    }
}

⭐2: 遞迴位元加法#

• 概念: 與迭代法相同的邏輯，用遞迴表達更簡潔
• 時間複雜度: O(32) = O(1)
• 空間複雜度: O(32) = O(1) - 遞迴深度

class Solution {
    fun getSum(a: Int, b: Int): Int {
        if (b == 0) return a
        return getSum(a xor b, (a and b) shl 1)
    }
}

在某些語言中（如 Python），負數的位元操作需要特別處理，因為 Python 的整數沒有固定位數。Kotlin/Java 使用 32-bit 補數表示法，天然支援負數的位元加法。

class Solution {
    fun getSum(a: Int, b: Int): Int {
        var x = a
        var carry = b
        while (carry != 0) {
            val tmp = x xor carry
            carry = (x and carry) shl 1
            x = tmp
        }
        return x
    }

    fun getSubtract(a: Int, b: Int): Int {
        return getSum(a, getSum(b.inv(), 1))
    }
}

🔑 Takeaways#

• Pattern: 用位元操作模擬算術運算，理解硬體層面的加法原理
• 關鍵技巧: XOR = 不進位加法、AND + 左移 = 進位計算，這是位元加法的核心公式