Day28 - 371.sum of two integers

Day28 - 371.两整数之和

LeetCode 371.两整数之和

题目链接：

https://leetcode.cn/problems/sum-of-two-integers/

1. 题目描述

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

举个例子：

输入：a = 1, b = 2
输出：3

2. 思路解析

正常的十进制加法是加数和被加数每一位相加然后加上上一位的进位数，大于10就继续进位。 题目要求不使用加法运算符，所以我们只能通过异或（^）、与（&）、左移（<<）等位运算来实现。

加数和被加数对应的二进制按位相加，1 + 1对应位变成0，1 + 0对应位变成1，0 + 0对应位变成0，这个可以通过异或（^）运算来实现。

那么还有进位怎么处理呢？

继续观察会发现加数和被加数对应的二进制按位相加，只有1 + 1会存在进位1，可以通过与（&）和左移（<<）运算来实现。

根据上述规律，对于a，b两个整数，我们可以得到算法如下：

1. temp_add = a ^ b，获取到每一位的和（不包含进位），进入步骤2。

2. temp_carry = (a & b) << 1，获取到每一位的进位，进入步骤3。

3. 如果进位temp_carry为0，最终结果就是temp_add。如果进位temp_carry不为0，a = temp_add，b = temp_carry，进入步骤1。

3. C++代码

class Solution
{
public:
    int getSum(int a, int b)
    {
        while (b)
        {
            // 计算 a 和 b 每位的和
            int add = a ^ b;
            // 计算 a 和 b 的进位
            unsigned int carry = (unsigned int)(a & b) << 1;
            // 如果进位为 0，直接返回位和
            if (carry == 0)
            {
                return add;
            }
            // 问题于是转化为 add + carry = ？
            // 变成了新的 a + b
            a = add;
            b = carry;
        }
        return a;
    }
};

本质上还是递归问题。

和运算：异或 ^

进位运算：与 &

4. 复杂度分析

时间复杂度： O(1)，因为整数在32位操作系统上占32位，最多计算32次temp_carry，故为常数的时间复杂度。

空间复杂度： 只使用了几个整型变量，故空间复杂度为O(1)。

5. Redo. 02/06

循环实现。只有一开始是a+b，后面都是加和结果 + 进位结果

• ^表示加和

• &表示进位（需要左移）

class Solution
{
public:
    int getSum(int a, int b)
    {
        while(b)
        {
            int temp_add = a ^ b;
            unsigned int temp_carry = (unsigned int)(a & b) << 1;
            a = temp_add;
            b = temp_carry;
        }
        return a;
    }
};