chuck

# 剑指Offer题解 - Day48

# 剑指 Offer 65. 不用加减乘除做加法

力扣题目链接 (opens new window)

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

示例:

输入: a = 1, b = 1
输出: 2
1
2

提示：

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

思路：

本题的本质其实就是使用逻辑门实现两数之和。在计算机原理的课程当中，应该会有所接触。下面就来仔细分析。

首先有两个重要的前提条件：

  1. 两个数均为整数，所以不需要考虑小数的计算逻辑。
  2. 两个整数可能为负数或者 0 。

接下来就使用位运算来进行两数相加。首先两个二进制数字相加，遵循以下规律：

a b 无进位和 进位
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
  1. 无进位和 跟 异或运算 的结果相等。
  2. 进位 跟 与运算 的结果相等。进位计算完成后需要左移一位，否则就是计算的当前位了。

# 位运算

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var add = function(a, b) {
    while(b) { // 当进位为 0 时跳出
        let c = (a & b) << 1; // 计算进位
        a = a ^ b; // 计算无进位和
        b = c; // 将进位赋值给b
    }
    return a;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 时间复杂度 O(1)。
  • 空间复杂度 O(1)。

分析：

根据刚才的思路分析，可以得出：a + b 等于 无进位和 + 进位。由于我们不能使用四则运算，因此这里需要将计算出来的结果赋值给a和b 。最终当 进位 b为0时，此时 无进位和 a就是最终结果。

位运算的时间和空间复杂度都是常数级别，因此都是O(1) 。

# 总结

本题考查位运算来求两数之和。其中核心结论是：

  1. 无进位和 跟 异或运算 的结果相等。
  2. 进位 跟 与运算 的结果相等。

剑指Offer题解 - Day49