題⽬描述

寫⼀個函數，求兩個整數之和，要求在函數體內不得使⽤ + 、 - 、 * 、 / 四則運算符號。

示例1
輸⼊：1,2
返回值：3

思路及解答

位運算迭代法（推薦）

將加法分解為「無進位和」+「進位值」，循環直到進位為0

位運算加法的數學原理：

• 異或運算 (^)：實現無進位加法

  • 0^0=0, 0^1=1, 1^0=1, 1^1=0（進位丟失）

• 與運算 (&)：檢測需要進位的位置

  • 只有1&1=1，其他情況都為0
• 左移運算 (<<)：將進位值移到正確位置

public class Solution {
    public int add(int a, int b) {
        // 循環直到進位為0
        while (b != 0) {
            // 計算無進位和：異或運算相當於無進位加法
            // 例如：5^3=6 (101^011=110)
            int sum = a ^ b;
            
            // 計算進位值：與運算後左移1位得到進位
            // 例如：(5&3)<<1=2 (101&011=001, 左移1位=010)
            int carry = (a & b) << 1;
            
            // 更新a為無進位和，b為進位值
            a = sum;
            b = carry;
            
            // 繼續下一輪計算，直到進位為0
        }
        return a;
    }
}

• 時間複雜度：O(1) - 最多循環32次（整數位數）
• 空間複雜度：O(1) - 只使用常數空間

位運算遞歸法

將迭代過程轉為遞歸調用，基礎案例是進位為0

public class Solution {
    public int add(int a, int b) {
        // 遞歸終止條件：當進位為0時，直接返回無進位和
        if (b == 0) {
            return a;
        }
        
        // 遞歸過程：計算無進位和與進位值，繼續遞歸相加
        return add(a ^ b, (a & b) << 1);
    }
}

• 時間複雜度：O(1) - 遞歸深度最多32層
• 空間複雜度：O(1) - 但遞歸棧有深度限制

遞歸案例：

add(2, 3)
  → add(2^3, (2&3)<<1) = add(1, 2)
    → add(1^2, (1&2)<<1) = add(3, 0)
      → b=0, 返回3
最終結果：5

投機取巧

import java.util.concurrent.atomic.AtomicInteger;

public class Solution {
    // 方法1：使用內置的加法方法
    public int add1(int a, int b) {
        return Integer.sum(a, b); // 內部實現還是用+，不符合要求
    }
    
    // 方法2：使用AtomicInteger（實際開發中更不實用）
    public int add2(int a, int b) {
        AtomicInteger ai = new AtomicInteger(a);
        return ai.addAndGet(b); // 內部使用CAS操作
    }
    
    // 方法3：使用BigDecimal（過度設計）
    public int add3(int a, int b) {
        // 需要創建對象，性能較差
        return BigDecimal.valueOf(a)
                .add(BigDecimal.valueOf(b))
                .intValue();
    }
}