不使用基本运算符实现两个数加法

不使用基本运算符实现两个数加法

Posted by Jae on March 16, 2020

1、题目

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

  示例:

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

提示:

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

2、思路

对于计算两个十进制数加法时如13+9,我们可以先计算不进位下的和,所谓不进位就是不考虑进位对结果造成的影响, 13+9在不考虑进位时为

1 3 0 9

13+9不考虑进位后为21+0进位后为1,所以就是12

13+9只考虑进位后为1+0向前一位进了03+9向前一位进了1,然后对结果x10就是01x10=10

然后再计算12+10

1 2 1 0

12+10不考虑进位为22

12+10只考虑进位为0000x10=0

然后计算22+0=22

计算机底层计算加法是通过门电路完成,我们计算下二进制下的加法,13=(1101)2 9=(1001)2

1101+1001不考虑进位为0100

1101+1001考虑进位为1001,然后左移既最低位补010010

然后计算00100+10010

00100+10010不考虑进位为10110

00100+10010考虑进位为00000,左移一位为000000

然后计算10110+000000=10110

(10110)2=22

3 实现

// 递归
public int add(int a, int b) {
    if (a == 0){
        return b;
    }else if (b == 0){
        return a;
    }else{
        return add(a^b, (a&b)<<1);
    }
}
// 非递归
public int add(int a, int b) {
    while(b != 0){
      int t = a^b;
      b = (a&b)<<1;
      a = t;
    }
    return a;
}