Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
思路:
这道题让我们实现两数相加,但是不能用加号或者其他什么数学运算符号,那么我们只能回归计算机运算的本质,位操作Bit Manipulation,我们在做加法运算的时候,每位相加之后可能会有进位Carry产生,然后在下一位计算时需要加上进位一起运算,那么我们能不能将两部分拆开呢,我们来看一个例子759+674
如果我们不考虑进位,可以得到323
如果我们只考虑进位,可以得到1110
我们把上面两个数字假期323+1110=1433就是最终结果了
然后我们进一步分析,如果得到上面的第一第二种情况,我们在二进制下来看,不考虑进位的加,0+0=0, 0+1=1, 1+0=1, 1+1=0,这就是异或的运算规则,如果只考虑进位的加0+0=0, 0+1=0, 1+0=0, 1+1=1,而这其实这就是与的运算,而第三步在将两者相加时,我们再递归调用这个算法,终止条件是当进位为0时,我们直接返回第一步的结果,参见代码如下:
var getSum = function(a, b) {
if(b===0) return a;
var sum=a^b;
var carry=(a & b) << 1;
return getSum(sum,carry);
};