不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

这道题看起来非常有趣，既然做加法，但却不让使用+、-、*、/四则运算符号，很多同学看了一眼就懵逼了，这可难倒八戒了。

我们来分析一下，如果不让用四则运算符合，那显然就是用递归了。为啥呢？原因很简单，递归程序里可以不需要运算符合，只要有递归结束条件即可。

举个例子，比如2+3=？

2用二进制表示是0010

3用二进制表示是0011

不用四则运算，我们就该想到使用逻辑运算符，与、或、非、异或，同或等。

显然，我们需要用到与、异或

异或相当于不带进位的加法：

1^0=1,

0^1=1,

0^0=0，

1^1=0

也就是：

与运算符正好我们可以用来求进位：

1&0=0,

0&1=0,

0&0=0，

1&1=1  （此时进位）

num4是两数做与操作后得到的结果左移一位。为啥需要左移一位呢，哈哈，原因很简单，进位嘛，向高位进位，当然要左移啦！

如上面两图所示，num3代表不进位的加法得到的结果，num4是进位得到的值。二者相加，就是最终结果，而题目要求不能使用加法，因此，我们就继续递归啊！（原因是咱们的递归程序就是在做加法操作）

那么最重要的问题来了，递归程序的结束条件是什么呢？

当进位为0时，直接返回num3就可以了！代码如下：

int Add(int num1, int num2) 
{     
        if(num2 == 0) 
        { // 进位为0时，返回
            return num1;
        }
        int num3 = num1 ^ num2; // 不考虑进位
        int num4 = (num1 & num2) << 1; // 进位
        return Add(num3, num4); 
}

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=1237