剑指Offer题解 - Day48

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

力扣题目链接[1]

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

「示例:」

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

「提示：」

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

思路：

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

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

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

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

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;
};

• 时间复杂度 O(1)。
• 空间复杂度 O(1)。

分析：

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

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

总结

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

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

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vz6d1/