3-不用运算符也能做加法？？｜刷题打卡

第三波打卡，选了一道看似Easy实则Medium可能是Hard的算法，为什么呢？因为难就难在思路上，请看：

一、先看题

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

示例：

返回如下的二叉树：

提示：

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

二、整理思路

第一时间我是懵逼的，不用运算符号我要怎么算？心算吗？客户端输入之后，传递到后台，咱们后台的程序猿心算之后输出答案并返回？

后来想想，计算机的语言和我们并不一样，我们平时使用的编程语言都是高级语言，是为了方便开发者使用的，运算符也是这样，如果不用运算符，那么只能从更底层的代码入手，看起来是跟二进制过不去了。

有了初步思路，听到二进制就立马联想到了位运算，可是到了这里就再也进行不下去了。

参考了题解之后，才意识到，原来是这么一回事！看来以后还要加强观察力的锻炼。

最主要的一个思路就是通过位运算来获取我们需要得到的答案的二进制代码。所以分析可以得：

设两数字的二进制形式 a, b，其求和 s = a + b ，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：

怎么样！有没有发现什么？

没错！两位数相加，他们的无进位和的结果居然和异或运算的规律是一样的！而进位则和与运算的规律相同！简直Amazing！

但是需要注意的是，进位规律是相同了，但是值还有些差别，因此我们还要用上左移位运算符，这样才能保证最终结果是一致的。

根据以上的分析，我写出了以下代码

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var add = function (a, b) {
    let benwei = a ^ b
    let jinwei = (a & b) << 1
    if (b == 0) return a
    return add(benwei, jinwei)
};

由于计算机系统中的数值一律采用补码来表示和存储，因此即使有负数相加，依然可以保证结果的正确性。

三、总结

这类涉及到更底层的操作的题目，有时候会因为我们平时对底层逻辑的忽略而成为拦路虎，因此在平时学习和工作的过程中，应该尽量了解自己所接触的知识的实现逻辑，这样才能更好地处理一些看起来似乎不可能的任务。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情