題目描述:不使用 + 或 - 運算符,計算兩個整數 a 和 b 的和。
解題思路:用位元運算模擬全加器。a XOR b 計算各位不進位的和;(a AND b) << 1 計算進位。反覆將這兩個結果相加(進行同樣的位元運算),直到進位為 0 為止。此過程模擬了硬體全加器的邏輯:每次迭代處理一輪進位傳播。
時間複雜度:O(1) — 整數為 32 位元,迴圈最多執行 32 次。
空間複雜度:O(1) — 只用常數個變數。
1. While b != 0: a. carry = (a AND b) left-shifted by 1 b. a = a XOR b (sum without carry) c. b = carry 2. Return a
遞迴:getSum(a^b, (a&b)<<1) — 邏輯相同但遞迴形式。優雅但有堆疊溢位風險(實際中限於 32 次迭代)。
使用減法技巧:a - (-b) 但這違反題意。