Python 算法设计(2) - 大数运算 - 基于字符串的数字运算和进位

如果数字太大，不能将字符串转换为整数类型的时候，怎么运算数字呢？

原题

给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和。

注意：

• num1 和 num2 的长度都小于 5100.

• num1 和 num2 都只包含数字 0-9. - num1 和 num2 都不包含任何前导零。

• 你不能使用任何内建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

代码实现

程序从num1, num2的最后一位数开始，依次计算num1, num2同一数位的数字之和，如果和大于10，则进位。

要点：

• add=s//10需要放在s=a1+a2+add之后，这样下一次计算才能获得前一次计算的进位。
• 计算完最后一个num1, num2的数位后，如果有进位，计算结果还需要加上进位。

def solution(nums):
    num1,num2=nums
    if len(num1)<len(num2):
        num1,num2=num2,num1 # 交换num1, num2变量
    num2=num2.zfill(len(num1)) # num2 的开头用0填充，使num2的长度等于num1的长度
    result=""
    add=0
    for i in range(-1,-len(num2)-1,-1):
        a1,a2=int(num1[i]),int(num2[i])
        s = a1 + a2 + add
        #print(a1,a2,s)
        result = str(s%10) + result
        add=s//10 # 下一位的进位

    if add>0:
        result=str(add)+result # 计算结果加上最后一个进位

    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

写完代码后，还需要进行测试。这里使用random模块，随机产生两个整数，进行计算。

from random import randint
for i in range(1000):
    num1,num2=str(randint(0,10000)),str(randint(0,10000))
    result=solution([num1,num2])
    if result != str(int(num1)+int(num2)):
         raise Exception("计算错误: %s %s %s"%(num1,num2,result))
    else:
        print("计算正确: %s %s %s"%(num1,num2,result))
1
2
3
4
5
6
7
8

部分运行结果：

计算正确: 3910 3129 7039
计算正确: 1018 4859 5877
计算正确: 3055 7940 10995
计算正确: 1018 1904 2922
计算正确: 4657 3795 8452
计算正确: 393 6770 7163
计算正确: 2512 2379 4891
计算正确: 5701 1903 7604
1
2
3
4
5
6
7
8

注：题目来自CSDN的“每日一练”习题功能。
有兴趣的读者，可以对程序进行相应的改编，如计算减法、乘法、除法等。