48.不用加减乘除做加法.md

48.不用加减乘除做加法

题目描述

• 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

 

解题思路

下面的思路来自《剑指offer》。

• 使用二进制加法运算原理。

  十进制运算的加法可以看出不进位相加，然后再加上进位的值，比如15+7=22就可以拆分成先进行15和7的不进位相加，得到12，然后再加上进位10，即12+10=22，即可得到最终结果。

  二进制相加也可以采用相同的方法。首先看第一步不进位相加，两位都是1和两位都是0的不进位相加结果都是0，只有两位不一样的时候不进位相加结果才是1，这个运算规则和异或是一样的，因此这一步可以用异或来替代；第二步，计算进位，只有两位都是1才需要进位，这个可以用与运算得到哪些位置要进位，然后把与运算的结果向左移一位即可得到进位的值，然后把进位值按相同的方法和第一步的结果相加，直到不产生进位为止。

 

代码

• 使用二进制加法运算原理。

class Solution {
public:
    int Add(int num1, int num2)
    {
        int sum = num1 ^ num2;
        int carry = (num1 & num2) << 1;
        while(carry != 0){
            num1 = sum;
            num2 = carry;
            sum = num1 ^ num2;
            carry = (num1 & num2) << 1;
        }
        return sum;
    }
};