今天是我坚持写题解的第 53 天！

题目描述（Medium）

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

示例 1：

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

示例 2：

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

提示：

-1000 <= a, b <= 1000

链接：https://leetcode-cn.com/problems/sum-of-two-integers

方法一、模拟加法

这道题我们能想到最简单的一种做法与模拟字符串加法一样，我们用二进制来模拟，这里要考虑进位的问题，思路比较简单。

请看代码：

class Solution {
    public int getSum(int a, int b) {
        int ans = 0;
        // 存储进位
        int carry = 0;
        for (int i = 0; i < 32; i++) {
            // 从低位到高位依次计算
            int x = (a >> i) & 1;
            int y = (b >> i) & 1;
            if (x == 1 && y == 1) {
                // 不管carry是啥，肯定有进位
                ans |= carry << i;
                carry = 1;
            } else if (x == 1 || y == 1) {
                // carry为1则有进位，carry为0则无进位，与现有的carry一致
                ans |= (carry ^ 1) << i;
            } else {
                // 不管carry是啥，肯定没有进位
                ans |= carry << i;
                carry = 0;
            }
        }
        return ans;
    }
}

复制

• 时间复杂度：O(C)，C固定为32。
• 空间复杂度：O(1)。

运行结果：

方法二、迭代法

我们观察位运算中的 &
和 ^
：

^
运算，又称作无进位加法，通过 ^
运算我们可以得到在不考虑进位条件下的加法结果。

通过 &
运算，我们可以确定哪些位置是需要进位的，把这些位置左移一位，再与异或的结果求和就可以得到结果。

比如，上图中计算的结果（注意，&运算的结果左移一位）：

但是我们又不能直接使用加法， 所以，我们可以通过不断迭代完成这个过程。

请看代码：

class Solution {
    public int getSum(int a, int b) {
        // 011011 011100 011010 010010 000010 100010
        // 000111 000110 001000 010000 100000 000000
        int carry;
        while (b != 0) {
            carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

复制

• 时间复杂度：O(C)，C最多为32。
• 空间复杂度：O(1)。

运行结果：

最后

如果对你有帮助，请点个赞吧，谢谢^^

也可以关注我，每日分享题解，一起刷题，一起拿全家桶。