面试题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;
}