371. Sum of Two Integers

Problem

Given two integers a and b, return the sum of the two integers without using the operators + and -.

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

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

• -1000 <= a, b <= 1000

Test Cases

1
2

class Solution:
    def getSum(self, a: int, b: int) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import pytest

from solution import Solution


@pytest.mark.parametrize('a, b, expected', [
    (1, 2, 3),
    (2, 3, 5),

    (100, 200, 300),
    (-100, -200, -300),
    (-100, 150, 50),
    (-200, 150, -50),

    (-1, 1, 0),
    (-1, 0, -1),
])
class Test:
    def test_solution(self, a, b, expected):
        sol = Solution()
        assert sol.getSum(a, b) == expected

Thoughts

看单个二进制位（其中 r 表示相加结果的低位，c 表示进位）：

$$\begin{array}{cc:cc} a & b & c & r \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array}$$

所以 $r=a\oplus b$，$c=a\land b$。c 比 r 要靠左一位，可以令 $c=(a\land b)\ll 1$。

更多的二进制位也是类似的，得到 $a+b=r+c=(a\oplus b)+((a\land b)\ll 1)$。

再对 r 和 c 按照相同的逻辑运算，知道待相加的两个数至少有一个变为 0（一般看 c）（TODO：最多循环多少次？）。

如果用 Python 实现就特殊一些，因为 Python 内置支持任意大的整数，负数的表达方式跟其他语言就不太一样，需要自行模拟其他语言里的有限二进制位整数。比如以 32 位为例，每次计算得到新的 r 和 c，需要跟一个 32 位的全 1 掩码做 bit-and，模拟普通的 32 位整数。返回计算结果前，如果结果是负数，也要再转换成 Python 格式的负数。

Code

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        while b != 0:
            a, b = a ^ b, (a & b) << 1
            a &= mask # Python specific.
            b &= mask # Python specific.

        if a & 0x80000000:
            a |= ~mask # Python specific.

        return a

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章