一:非递归解法
我们先来看一道非常简单的题,在计算机中数字是由二进制位表示的,也就是说是由0
和1
组成的,如果我们要实现0
和1
之间的加法该怎么实现呢,他会有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; }
a
和b
要么是1
要么是0
,所以这里最多也只有一个进位,很好理解。但我们计算二进制的加减法不光只有1
个0
或1,可能会有好多个1
或0
,那我们该怎么实现呢。比如a=13(1101)
,b=9(1001)
,我们该怎么计算a+b
的结果。首先如果我们不考虑进位问题,那么a+b
的运算会是下面这样
但实际上最前面和最后面的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=10110
,10110
实际上就是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; }
这个也很好理解,每次计算的时候要对a
和b
进行重新赋值,然后再不断的循环,直到b等于0的时候停止循环,我们知道这里在运算的时候b表示的是进位的值,当b等于0的时候就表示没有进位,没有进位就退出循环,这就是使用位运算来实现加法。我们假设a=13
,b=9
来画个图加深一下理解
其实我们还可以不使用“+”、“-”、“*”、“/”
符号来实现加法,减法,乘法,除法
。具体可以看下
截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666