給定兩個整數
a和b，在不使用+和-運算子的情況下，回傳兩整數之和。
Example:
Input: a = 1, b = 2 Output: 3
Intuition
TIP
核心思路：XOR 算不進位的和，AND 左移一位算進位，重複直到進位為 0。
- 二進位加法的本質：每一位的和等於 XOR（不考慮進位），進位等於 AND 再左移一位
- 將「本位和」和「進位」反覆合併，直到進位為 0
- 這就是硬體加法器（Ripple Carry Adder）的運作原理
Approaches
1. Iterative Bitwise Addition — O(32) / O(1)
- Idea: 用 XOR 計算不進位的和，AND + 左移計算進位，重複直到無進位
- Time:
O(32)=O(1)- 最多 32 次迭代 - Space:
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. Recursive Bitwise Addition — O(32) / O(32)
- Idea: 與迭代法相同的邏輯，用遞迴表達更簡潔
- Time:
O(32)=O(1) - Space:
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)
}
}WARNING
在某些語言中（如 Python），負數的位元操作需要特別處理，因為 Python 的整數沒有固定位數。Kotlin/Java 使用 32-bit 補數表示法，天然支援負數的位元加法。
Note: Bitwise Subtraction
減法 a - b 等於 a + (-b)，而 -b 在補數表示法中等於 ~b + 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
}
fun getSubtract(a: Int, b: Int): Int {
return getSum(a, getSum(b.inv(), 1))
}
}🔑 Takeaways
- Pattern: 用位元操作模擬算術運算，理解硬體層面的加法原理
- Key trick: XOR = 不進位加法、AND + 左移 = 進位計算，這是位元加法的核心公式