不用加减乘除做加法 ----《剑指offer》面试题47
程序员文章站
2022-07-10 20:22:14
...
题目
写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/ 四则运算符号。
思路
利用位运算实现加法运算。
假设这两个数是5(num1)和17(num2),5的二进制是101,17的二进制是10001。把计算分成三步:
(1) 将两个数进行异或操作,得到的结果是两个数相加,但没有考虑进位的结果 --> sum。
(2) 将两个数进行与操作,再将结果左移1位,得到的是5和17相加需要进位的数 --> carry。
(3) 继续将sum 与 carry 赋值给 num1, num2,继续(1)、(2)相加的步骤,将进位结果添加到原本的sum中。
(4) 不断循环直到没有进位。
代码
#include <iostream>
using namespace std;
int Add(int num1, int num2)
{
// sum 是不考虑进位,两数相加的和
// carry用于记录进位
int sum,carry;
do
{
sum = num1^num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}while(num2 != 0); // 当没有进位时,停止继续相加
return num1;
}
int main()
{
cout << "1 + 3 = " << Add(1,3) << endl;
return 0;
}