题⽬描述

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

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

思路及解答

位运算迭代法（推荐）

将加法分解为「无进位和」+「进位值」，循环直到进位为0

位运算加法的数学原理：

  • 异或运算 (^)：实现无进位加法

    • 0^0=0, 0^1=1, 1^0=1, 1^1=0（进位丢失）

  • 与运算 (&)：检测需要进位的位置

    • 只有1&1=1，其他情况都为0

  • 左移运算 (<<)：将进位值移到正确位置

  • 时间复杂度：O(1) - 最多循环32次（整数位数）

  • 空间复杂度：O(1) - 只使用常数空间

位运算递归法

将迭代过程转为递归调用，基础案例是进位为0

  • 时间复杂度：O(1) - 递归深度最多32层

  • 空间复杂度：O(1) - 但递归栈有深度限制

递归案例：

投机取巧