剑指Offer - 九度1507 - 不用加减乘除做加法
2013-11-29 20:00
- 题目描述：
-
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入为两个整数m和n(1<=m,n<=1000000)。
- 输出：
-
对应每个测试案例，输出m+n的值。
- 样例输入：
-
3 4
7 9
- 样例输出：
-
7
16
题意分析：
求两个数的和而不能用加减乘除，很明显又得借助位运算了。回想一下学Verilog时加法器的实现，能记住下面这两个关系：
sum = bit1 ^ bit2 ^ carry
carry' = (carry & bit1) | (bit1 & bit2) | (bit2 & carry)
其中sum是当前位的和，bit1和bit2是两数的当前二进制位，carry是上一位的进位，carry'是这一位的进位。
简单解释一下俩式子：
式子1：加法和异或的区别就在于加法可以进位，而异或不进位。
式子2：三个数只要有两个以上的‘1’就有进位了，所以是三个与的或。
接下来就是逐位相加，将进位carry一直向上传递了。要注意别让最高位的carry丢失掉，除非是超出了本身数据能表示的范围。
既然是写个加法器，依然本着写Verilog的原则，拒绝for循环。以下是ac的代码。
// 653474 zhuli19901106 1507 Accepted 点击此处查看所有case的执行结果 1020KB 1439B 10MS
//
#include <cstdio>
using namespace std; void cal_onebit(const int m, const int n, int i, int &carry, int &res)
{
res = (res |
(
(m & ( << i)) ^
(n & ( << i)) ^
(carry << i)
)
);
carry =
(
(m & ( << i)) &
(n & ( << i))
) ||
(
(n & ( << i)) &
(carry << i)
) ||
(
(carry << i) &
(m & ( << i))
);
} int main()
{
int m, n;
int res;
int carry; while(scanf("%d%d", &m, &n) == ){
carry = ;
res = ;
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
cal_onebit(m, n, , carry, res);
printf("%d\n", res);
} return ;
}