Cracking the coding interview--Q20.1

February 24, 2013
作者:Hawstein
出处:http://hawstein.com/posts/20.1.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Write a function that adds two numbers. You should not use + or any arithmetic operators.

译文:

写一个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

代码如下:

int Add2(int a, int b){
    if(b == 0) return a;
    int sum = a ^ b; // 各位相加,不计进位
    int carry = (a & b) << 1; // 记下进位
    return Add2(sum, carry); // 求sum和carry的和
}

递归的迭代版本如下:

int Add3(int a, int b){
    while(b != 0){
        int sum = a ^ b;
        int carry = (a & b) << 1;
        a = sum;
        b = carry;
    }
    return a;
}

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

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

得到目标数据地址:0xbfc86d98 + sizeof(int) * 1 = 0xbfc86d9c
取出0xbfc86d9中的数据

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

int Add1(int a, int b){
    char *c = (char*)a;
    return (int)&c[b]; // c+sizeof(char)*b=a + b
}

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

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

如果还想知道更多关于c语言的奇奇怪怪的点,推荐阅读《C陷阱与缺陷》。

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview