48 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解题思路

核心思想：使用位运算。加法可以分为两部分：不含进位的和（异或）+ 进位（与运算后左移）。

关键步骤：

1. 计算不含进位的和：a ^ b
2. 计算进位：(a & b) << 1
3. 将进位加到和上，重复直到进位为0

时间复杂度：O(1)（最多32位） 空间复杂度：O(1)

Python 实现

def add(a, b):
    """
    不用加减乘除做加法

    Args:
        a: 第一个数
        b: 第二个数

    Returns:
        int: 两数之和
    """
    while b:
        # 计算不含进位的和
        sum_without_carry = a ^ b
        # 计算进位
        carry = (a & b) << 1
        a = sum_without_carry
        b = carry

    return a


# 测试代码
if __name__ == "__main__":
    test_cases = [
        (1, 2),
        (10, 20),
        (-1, 1),
        (-5, 3),
    ]

    for a, b in test_cases:
        print(f"{a} + {b} = {add(a, b)}")

# 输出:
# 1 + 2 = 3
# 10 + 20 = 30
# -1 + 1 = 0
# -5 + 3 = -2

图解

示例: a=1(001), b=2(010)

第一轮:
sum_without_carry = 1 ^ 2 = 3 (011)
carry = (1 & 2) << 1 = 0
a=3, b=0

b=0, 结束, 返回3

---

示例: a=5(101), b=3(011)

第一轮:
sum_without_carry = 5 ^ 3 = 6 (110)
carry = (5 & 3) << 1 = 2 (010)
a=6, b=2

第二轮:
sum_without_carry = 6 ^ 2 = 4 (100)
carry = (6 & 2) << 1 = 4 (100)
a=4, b=4

第三轮:
sum_without_carry = 4 ^ 4 = 0 (000)
carry = (4 & 4) << 1 = 8 (1000)
a=0, b=8

第四轮:
sum_without_carry = 0 ^ 8 = 8 (1000)
carry = (0 & 8) << 1 = 0
a=8, b=0

b=0, 结束, 返回8