C++版 - 剑指offer 面试题47：不用＋、－、×、÷做加法 题解
C++版 - 剑指offer 面试题47：不用＋、－、×、÷做加法 题解
面试题47：不用加减乘除做加法
提交网址： http://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201
时间限制：1秒 空间限制：32768K 参与人数：2147
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
分析： 此题属发散思维能力的题型。
看到的这个题目，我的第一反应是懵了，四则运算都不能用，那还能用什么呢？不过化为二进制数之后，用位运算 与&、或|、异或^、取反~可以派上用场。
首先看十进制是如何做的： 9+19=28，使用分3步走的策略。 对应与函数int Add(int num1, int num2)，此时num1=9, num2=19 第1步：相加各位的值，不算进位，得到不计进位的和sum=18(共2位)。 第2步：计算进位值，得到与进位等价的数carry=10. (如果这1步的进位值为0，那么第1步得到的值就是最终结果，否则继续第3步。) 第3步：重复上述两步，只是相加的值变成上述两步的得到的结果num1=18和num2=10，无进位，此时Add()的num2=0，结束。(如果还有进位，重复上述两步。) 同样我们可以用3步走的方式计算二进制值相加： 9->1001(num1)，19->10011(num2) 第1步：不计进位地各位相加，得到11010，二进制每位相加就相当于各位做异或操作，sum=01001^10011=11010。 第2步：计算进位值，得到10，相当于各位做与操作得到1，再向左移一位得到00010，carry=(01001&10011)<<1=10。 第3步：重复上述两步， 不计进位地各位相加：11010^00010=11000，进位值为100=(11010&00010)<<1。 继续重复上述两步：11000^100 = 11100，进位值carry为0，此时Add()的num2=0，结束，11100(十进制28)为最终结果。
递归实现 AC代码：
#include<cstdio>
using namespace std;
class Solution {
public:
int Add(int num1, int num2)
{
int sum, carry;
sum=num1^num2; // 按位异或表示各位分别相加，不计入进位
carry = (num1 & num2) << 1; // carry用0、1来记录各bit的进位
if(num2==0) return num1; // 递归出口
return Add(sum, carry);
}
};
// 以下为测试
int main()
{
Solution sol;
int res1 = sol.Add(3,6);
int res2 = sol.Add(-5, 256);
printf("%d\n", res1);
printf("%d\n", res2);
return 0;
}迭代实现 AC代码：
#include<cstdio>
using namespace std;
class Solution {
public:
int Add(int num1, int num2)
{
int sum, carry;
while(num2 != 0) // 当被加数为0时，迭代找到了结束出口
{
sum = num2 ^ num1; // 按位异或表示各位分别相加，不计入进位
carry = (num1 & num2) << 1; // carry用0、1来记录各bit的进位
num2 = carry;
num1 = sum;
}
return num1;
}
};
// 以下为测试
int main()
{
Solution sol;
int res1 = sol.Add(3,6);
int res2 = sol.Add(-5, 256);
printf("%d\n", res1);
printf("%d\n", res2);
return 0;
}