一:非递归解法

我们先来看一道非常简单的题,在计算机中数字是由二进制位表示的,也就是说是由01组成的,如果我们要实现01之间的加法该怎么实现呢,他会有4种组合方式

1,0+0=00

2,0+1=01

3,1+0=01

4,1+1=10

我们发现一个很重要的规律,就是只有1+1有进位,其他的都没进位。所以我们判断有没有进位只需要判断a&b是否等于1即可,而a+b的值(不考虑进位)只需要计算a|b即可,看明白了这点,代码就呼之欲出了

     public int add(int a, int b) {
        int c = (a & b) << 1;//进位的值
        int d = a ^ b;//不考虑进位,相加的值
        return c | d;//或者 return c ^ d;
    }

ab要么是1要么是0,所以这里最多也只有一个进位,很好理解。但我们计算二进制的加减法不光只有10或1,可能会有好多个10,那我们该怎么实现呢。比如a=13(1101)b=9(1001),我们该怎么计算a+b的结果。首先如果我们不考虑进位问题,那么a+b的运算会是下面这样

image.png

但实际上最前面和最后面的1都有了进位。


1,我们看到如果不考虑进位,那么a+b的结果其实就是a^b的结果,我们该怎么把进位问题也考虑在内呢,实际上只有1+1的时候才会出现进位1+0或者0+0都不会出现进位,所以我们首先想到的是&运算

2,这里我们计算一下a&b的结果是1001,我们知道当&运算的结果为1的时候,说明参与&运算的两个都是1,既然两个都是1,那么相加的时候就肯定会有进位,所以他们进位的值实际上是10010((a&b)<<1),然后在和0100相加就是我们要求的结果,10010+00100=1011010110实际上就是22,也就是13+9的结果

3,但我们好像忽略了一个问题,就是这道题要求不能使用加减乘除符号,而上面我们分析的时候使用了加号,所以明显不行。通过上面的分析实际上我们已经发现了一个规律,就是a+b通过^&运算之后又再执行相加操作,所以我们首先想到的是递归,我们来看下代码

public int Add(int a, int b) {
    if (a == 0 || b == 0)
        return a ^ b;
    return Add(a ^ b, (a & b) << 1);
}

3行表示的是如果a==0就返回b,如果b==0就返回a,这种写法少了一个if语句的判断会更简洁

看一下运行结果

图片说明


2,递归解法

上面的递归我们还可以改为非递归的方式

public int Add(int a, int b) {
    while (b != 0) {
        int temp = a ^ b;
        b = (a & b) << 1;
        a = temp;
    }
    return a;
}

这个也很好理解,每次计算的时候要对ab进行重新赋值,然后再不断的循环,直到b等于0的时候停止循环,我们知道这里在运算的时候b表示的是进位的值,当b等于0的时候就表示没有进位,没有进位就退出循环,这就是使用位运算来实现加法。我们假设a=13b=9来画个图加深一下理解

image.png

其实我们还可以不使用“+”、“-”、“*”、“/”符号来实现加法,减法,乘法,除法。具体可以看下

《不使用“+”,“-”,“×”,“÷”实现四则运算》


截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的《牛客博客》查看更多的详细题解