题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 ＋、－、×、÷ 四则运算符号。

数据范围

−1000≤num1,num2≤1000

样例

输入：num1 = 1 , num2 = 2
输出：3

方法一：位运算 O(1)

这道题可以总结为下面这个公式：

答案 = 没进位的和 + 进位 答案 = 没进位的和 + 进位答案=没进位的和+进位

这样一看可能会云里雾里的，我们来举个例子，假设 num1 二进制表示为 0 0 1 1 1 0 ，num2 二进制表示为 1 0 1 0 1 1 ，那么两者相加结果如下：

num1 = 0 0 1 1 1 0

num2 = 1 0 1 0 1 1

nums = 1 1 1 0 0 1

但是题目要求不能用到加法，所以我们可以将加法步骤进行拆分，分为没进位的和 sum 以及进位的数 carry ：

sum = num1 ^ num2 = 1 0 0 1 0 1

carry = ( num1 & num2 ) << 1 = ( 0 0 1 0 1 0 ) << 1 = 0 1 0 1 0 0

可以发现，我们利用了异或和与运算的性质，可以得到 nums = sum + carry 。但前面说过了，不能用加法运算，所以我们只能将 num1 = sum, num2 = carry ：

num1 = sum = 1 0 0 1 0 1

num2 = carry = 0 1 0 1 0 0

然后再重复上述步骤直至 num2 = carry 为 0 即没有进位时，就能得到最终答案即 num1 = sum 。

class Solution {
public:
    int add(int num1, int num2) {
        while (num2)
        {
            int sum = num1 ^ num2;  //没进位和
            int carry = (unsigned int)(num1 & num2) << 1; //进位
            num1 = sum, num2 = carry;
        }
        return num1;
    }
};

欢迎大家在评论区交流~