20.1 不能使用+号或其它算术运算符求两个数的和

题目

写一个Add函数求两个数的和,不能使用+号或其它算术运算符。

解答

为了解决这个问题,让我们来深入地思考一下,我们是如何去加两个数的。为了易于理解, 我们考虑10进制的情况。比如我们要算759 + 674,我们通常从最低位开始加, 考虑进位;然后加第二位,考虑进位…对于二进制,我们可以使用相同的方法, 每一位求和,然后考虑进位。

能把这个过程弄得更简单点吗?答案是YES,我们可以把求两个数的和分成两步, “加"与"进位",看例子:

  1. 计算759 + 674,但不考虑进位,得到323。
  2. 计算759 + 674,只考虑进位,而不是去加每一位,得到1110。
  3. 把上面得到的两个数加起来(这里又要用到加,所以使用递归调用即可)

由于我们不能使用任何算术运算符,因此可供我们使用的就只有位运算符了。 于是我们把操作数看成二进制表示,然后对它们做类似的操作:

  1. 不考虑进位的按位求和,(0,0),(1,1)得0,(1,0),(0,1)得1, 使用异或操作可以满足要求。
  2. 只考虑进位,只有(1,1)才会产生进位,使用按位与可以满足要求。 当前位产生进位,要参与高一位的运算,因此按位与后要向左移动一位。
  3. 递归求和,直到进位为0

代码如下:

递归的迭代版本如下:

 

对于这道题目,还有一个非常巧妙的解法。我们知道,数组操作本质上其实是指针操作。 数组名其实是指向数组首元素地址的指针。比如说整数数组a,a[1]表示的是数组中的第 1个元素,这是一直以来我们的理解。而编译器看到a[1],它是怎么去理解的呢?

首先,它会用数组首元素地址,加上偏移量,得到目标数据的地址, 然后再把里面的数据按指针指向类型的大小取出。所以,当编译器看到a[1], 它实际上做了下面的事:假设a指向的地址为0xbfc86d98

从上面可以看出,操作数组元素其实隐含了加法!所以呢,如果我们要求两个数的和, 只需要把其中一个看成地址,另一个看成偏移量,然后用返回它们对应数组元素的地址即可。 看代码:

 

上述代码将a强制转换为指向char的指针c,然后返回c[b]的地址即可。c[b] 的地址就等于c + sizeof(char)*b = a + b。有人会问,它b是负数时OK吗? OK,没问题的。它代表偏移量为负,往反方向计算地址就是了。

由于编译器对数组的解释方式如上所述,因此上面代码中的c[b]也可以写成b[c],或 a[5]可以写成5[a],效果是一样的,因为编译器都会先去求地址和偏移量的和。

文/Hawstein

1 Likes

你目前的身份是游客,评论请输入昵称和电邮!