371. 两整数之和（Python）
2019-05-17 本文已影响0人
玖月晴
题目
难度：★★☆☆☆
类型：数学
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
解答
这道题目就是实现：
class Solution(object):
def getSum(self, num1, num2):
return num1 + num2
虽然这么写肯定是可以通过的，但是这个“+”就是题目想让我们实现的。
无符号整数相加
我们先来看一下无符号整数在计算机内部是如何进行加法计算的。
和十进制相同，二进制也是通过从低位到高位依次相加实现加法计算，这里我们编写了三个函数：
-
补零函数（add_zero）：为了将两个二进制数变成同样的长度，通过向较小数高位补零实现；
-
一位全加器（add_bit）：实现一位的加法计算，这个在数字电路中是实现加法计算的基础，它的输入有三个，其中两个是加数bit1和bit2（0或1），另一个是上一位的进位carry，输出有两个，一个是当前位的计算结果cur_res，另一个是当前计算的进位（cur_carry），状态转移矩阵为：
| bit1 | bit2 | carry | cur_res | cur_carry |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
- 一个4字节全加器（add_unsigned_nums）：通过组合多个一位全加器实现，实现两个无符号整数之和。
class Solution(object):
def getSum(self, a, b):
def add_zero(num1, num2):
"""
两个二进制字符串中较短的最高位补零，补到和较长的一样长度。
:param num1:
:param num2:
:return:
"""
if len(num1) > len(num2):
num2 = '0' * (len(num2) - len(num1)) + num2
elif len(num2) > len(num1):
num1 = '0' * (len(num1) - len(num2)) + num1
return num1, num2
def add_bit(bit1, bit2, carry):
"""
模拟数字电路，我们也来实现一个一位的全加器，这里我们输入和输出都是字符串形式。
:param bit1: 第一个数，0或1
:param bit2: 第二个数，0或1
:param carry: 上一步的进位
:return: cur_res: 当前位的计算结果
:return: cur_carry: 进位
"""
if bit1 == '0' and bit2 == '0': # 如果输入两个数均为零
cur_res = carry # 结果即为上一步进位
cur_carry = '0' # 当前进位是零
elif bit1 == '1' and bit2 == '1': # 如果输入两个数均为一
cur_res = carry # 结果还是上一步进位
cur_carry = '1' # 当前进位是一
else: # 如果输入一个是一，另一个是零
if carry == '0': # 此时如果上一步进位为零
cur_res = '1' # 当前结果是一
cur_carry = '0' # 进位是零
else: # 此时如果上一步进位为一
cur_res = '0' # 当前结果为零
cur_carry = '1' # 进位为一
return cur_res, cur_carry # 返回计算结果和进位
def add_unsigned_nums(num1, num2):
"""
相加两个无符号二进制整数（字符串）
:param num1:
:param num2:
:return:
"""
res = ''
carry = '0'
for bit1, bit2 in reversed(list(zip(num1, num2))):
cur_res, carry = add_bit(bit1, bit2, carry) # 计算当前位
res = cur_res + res
if carry == '1': # 如果还有进位
res = carry + res # 记得加到最高位
return res # 返回结果
def add_nums(num1, num2):
num1, num2 = bin(num1)[2:], bin(num2)[2:] # 十进制转二进制（字符串）
num1, num2 = add_zero(num1, num2) # 短数补零与长数对齐
res = add_unsigned_nums(num1, num2) # 二进制求和
return int(res, base=2)
return add_nums(a, b)
有符号整数
我们使用类似的方法，实现有符号32位整数的相加，这里需要注意的是，32位有符号整数的范围是-2^31 ~ 2^31-1，负数用补码表示；如果计算结果超过整数范围，说明计算结果为负数，需要进行换算。
下面已经为读者写好了函数，这里我们使用掩码进行当前计算位的选择，读者如果希望观察计算流程，可以把打印开关（print_log）打开。
def oct2bin(num):
"""
32位有符号整数转为对应的二进制字符串
:param num:
:return:
"""
mask = 0x01
res = ''
for i in range(32):
cur = '1' if num & mask != 0 else '0'
res = cur + res
mask = mask << 1
return res
class Solution(object):
def getSum(self, num1, num2, print_log=False):
print('当前加数为：{}'.format(oct2bin(num1)))
print('当前加数为：{}'.format(oct2bin(num2)))
ans = 0 # 结果变量
mask = 0x01 # 这个掩码是用来提取指定位的值的
carry = 0 # 进位
for i in range(0, 32): # 32位中遍历
a = num1 & mask # 提取当前位
b = num2 & mask # 提取当前位
c = carry # 提取上一步进位
carry = 0 # 当前步进位归零
if a ^ b != 0: # 如果两个计算数中有一个为一，另一个是零
if c == 1: # 上一步进位为一
carry = 1 # 则当前一定会产生进位，当前位计算结果为零，ans不用动
else: # 上一步进位为零
ans |= mask # 当前不产生进位，当前位计算结果为一
else: # 如果两个计算数中均为一或者均为零
if a & mask > 0: # 研究两个计算数均为一的情况
carry = 1 # 进位肯定是要的
if c == 1: # 如果上一步有一个进位
ans |= mask # 那么当前结果就是一
mask = mask << 1 # 我们把掩码向左移动一位，开始研究更高的一位
if print_log: # 打印记录
print('\n当前遍历到了从低向高第{}位。'.format(i))
print('当前掩码为：{}'.format(oct2bin(mask)))
print('当前加数一：{}'.format(oct2bin(a)))
print('当前加数二：{}'.format(oct2bin(b)))
print('当前结果为：{}'.format(oct2bin(ans)))
if ans > 0x7fffffff: # 这种情况说明可能得到了负数
return ans - 0xffffffff - 1 # 返回负数的计算结果
return ans # 返回最终结果
if __name__ == "__main__":
s = Solution()
print(s.getSum(1, 5, True))
刁钻技巧
网上流传一种一句话实现的递归调用法，供读者参考。
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
return a if b == 0 else self.getSum(a ^ b, (a & b) << 1)
如有疑问或建议，欢迎评论区留言~
