欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

不用加减乘除做加法 ----《剑指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;
}