面試經典：不用 +-*/ 實現整數加法

題目

實現 int add(int a, int b)，要求函數體內不使用 + - * / 任何算術運算符。

核心原理：模擬二進制列豎加法

二進制逐位相加分兩步：

1. 不進位和：a ^ b（異或，0+0=0, 1+0=1, 1+1=0）。
2. 進位：(a & b) << 1（與運算得出進位位，左移一位對齊高位）。

因此：a + b = (a ^ b) + ((a & b) << 1)。右側仍含 +，但可構造遞歸：

add(a, b) = add(a ^ b, (a & b) << 1)

終止條件：進位為 0 時，a ^ b 即為最終結果。

遞歸實現

int add(int a, int b) {
    if (!a) return b;                 // a 為 0 直接返回 b
    return add((a & b) << 1, a ^ b); // 進位、不進位和遞歸
}

迭代版本（避免棧溢出）

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1; // 計算進位
        a = a ^ b;                  // 不進位和
        b = carry;                  // 進位作為下一輪加數
    }
    return a;
}

測試用例

擴展思考

• 同理可實現減法：a - b = add(a, add(~b, 1))（二補數）。
• 乘法可用「移位 + 條件加法」模擬；除法用「試商 + 移位減法」。
• 此類位運算技巧常見於嵌入式無硬件乘除單元、加密算法、編譯器優化等場景。