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
class Solution:
def getSum(self, a: int, b: int) -> int:solution_test.py下载完整源码
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 表示进位):
所以 ,。c 比 r 要靠左一位,可以令 。
更多的二进制位也是类似的,得到 。
再对 r 和 c 按照相同的逻辑运算,知道待相加的两个数至少有一个变为 0(一般看 c)(TODO:最多循环多少次?)。
如果用 Python 实现就特殊一些,因为 Python 内置支持任意大的整数,负数的表达方式跟其他语言就不太一样,需要自行模拟其他语言里的有限二进制位整数。比如以 32 位为例,每次计算得到新的 r 和 c,需要跟一个 32 位的全 1 掩码做 bit-and,模拟普通的 32 位整数。返回计算结果前,如果结果是负数,也要再转换成 Python 格式的负数。
Code
solution.py下载完整源码
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
评论需要 JavaScript。