首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

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

2013-10-07 
写一个Add函数求两个数的和,不能使用+号或其它算术运算符问题:写一个Add函数求两个数的和,不能使用号或其

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

问题:写一个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陷阱与缺陷》。

热点排行