Cracking the coding interview--Q20.1

题目

原文：

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

译文：

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

解答

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

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

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

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

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

声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处

出处：http://hawstein.com/2013/02/24/20.1/

题目

解答

FEATURED TAGS