python整数运算

Python超长整数运算

• ！！！！！
• 非负整数运算
• 整数运算

！！！！！

如果大家有更好的想法，或者发现了BUG，一定要告诉我哦。

非负整数运算

这次，我们加法采用对位相加，也就是两个长整数对应位上的数字相加，之后再计算进位，最后得出结果的方法。

非负整数相加-对位相加

例如	数字
被加数	1111
加数	99999

先将数字串分割为独立的数字,再对位相加。

···	十万	万位	千位	百位	十位	个位
被加数	0	0	1	1	1	1
+	+	+	+	+	+	+
加数	0	9	9	9	9	9
结果	0	9	10	10	10	10

之后是处理进位。

···	十万	万位	千位	百位	十位	个位
个位进位	0	9	10	10	10+1	←0
十位进位	0	9	10	10+1	←1	0
百位进位	0	9	10+1	←1	1	0
千位进位	0	10	←1	1	1	0
万位进位	0+1	←0	1	1	1	0
最终结果	1	0	1	1	1	0

上代码：

# 非负大整数相加 def SUM(NUM1, NUM2): # 分割数字字符串 num1 = list(NUM1) num2 = list(NUM2) # 分割字符串从右对齐逐个相加存入temp len1 = len(num1) len2 = len(num2) count = max(len1, len2) index = 0 temp = [0 for i in range(count+1)] if len1 > len2: # 哪个数更长的操作 index = len2-1 else: index = len1-1 for i in range(count, 0, -1): if len1 > len2: if index >= 0: temp[i] += int(num2[index]) index -= 1 temp[i] += int(num1[i-1]) else: if index >= 0: temp[i] += int(num1[index]) index -= 1 temp[i] += int(num2[i-1]) # 判断是否有进位 for i in range(count, -1, -1): if temp[i] > 9: temp[i] = temp[i] % 10 temp[i-1] += 1 temp[i] = str(temp[i]) # 判断结果是否有0前缀,有则去除 while temp[0] == "0": if len(temp) == 1 and temp[0] == 0: return 0 temp.pop(0) count -= 1 # 大整数连接起来 Sum = '' for i in range(count+1): Sum += temp[i] return Sum 

加数和被加数倒过来也一样，但是涉及到谁的位数更大一些，代码上需要判断一下，因为代码中保存对位相加结果的变量temp[]的长度是按最长的整数的长度而定的(多一位，因为可能会进位)。

非负整数相减-对位相减

整数相减不同于相加，被减数和减数不能随意颠倒位置，但是我们仍可以使用对位相减的方法，只是需要限制。
减法，实质上是求两个数的距离，例如:

$$9999-91111=-(91111-9999)$$

那么这样的话，我们可以将更大的数字始终作为被减数，只需要在结果判断是否添加负号即可。

例如	数字
被减数	9999
减数	91111

同加法，分割字符,但是减数更大，将减数变成被减数，被减数变为减数，结果添负：

···	符号	万位	千位	百位	十位	个位
被减数	-	9	1	1	1	1
-		-	-	-	-	-
减数	-		9	9	9	9
结果	-	9	-8	-8	-8	-8

之后是处理借位。

···	符号	万位	千位	百位	十位	个位
结果	-	9	-8	-8	-8-1→	10-8
结果	-	9	-8	-8-1→	10-9	2
结果	-	9	-8-1→	10-9	1	2
结果	-	9-1→	10-9	1	1	2
最终结果	-	8	1	1	1	2

那么问题来了！ 能不能小的减大的呢，这不省掉了判断大小那一步吗？

我们试一试：

···	符号	万位	千位	百位	十位	个位
被减数	+		9	9	9	9
-		-	-	-	-	-
减数	+	9	1	1	1	1
结果	+	-9	8	8	8	8

之后是处理借位，这里我发现一个规律，就是最高位是负的，需要向更高位借位，但是没有更高位了，头秃。

但是，我发现将结果每位都取负，然后结果符号也取负。

结果如下：

···	符号	万位	千位	百位	十位	个位
结果	-	9	-8	-8	-8	-8
最终结果	-	8	1	1	1	2

头秃，是可以的。但是也OK，代码也被简化了，上代码：

# 非负大整数相减，减法实质上是求两个数字的距离 def SUB(NUM1, NUM2): # 分割数字字符串 num1 = list(NUM1) num2 = list(NUM2) # 分割字符串从右对齐长(大)减短(小)存入temp len1 = len(num1) len2 = len(num2) count = max(len1, len2) index = 0 symbol = 0 temp = [0 for i in range(count)] if len1 > len2: index = len2 - 1 else: index = len1 - 1 for i in range(count-1, -1, -1): if len1 > len2: if index >= 0: temp[i] -= int(num2[index]) index -= 1 temp[i] += int(num1[i]) else: if index >= 0: temp[i] += int(num1[index]) index -= 1 temp[i] -= int(num2[i]) # 判断结果是否有0前缀,有则去除 while temp[0] == 0: if len(temp) == 1 and temp[0] == 0: return 0 temp.pop(0) count -= 1 # 符号置换，使最高位能够借位给低位 if temp[0] < 0: symbol = 1 for i in range(count): temp[i] = temp[i] * (-1) # 判断借位 for i in range(count-1, -1, -1): if temp[i] < 0: temp[i] += 10 temp[i-1] -= 1 # 添加结果符号 if symbol == 1: sub = "-" for i in range(count): sub += str(temp[i]) return sub else: sub = "" for i in range(count): sub += str(temp[i]) return sub 

非负整数相乘

整数相乘听上去很唬人,但是只要我们把我们平常使用的方法，转化为代码思想，其实不算难，只需注意几点就行。

大家手算乘法的时候，是怎么算的呢？我觉得我们应该都一样，是用的这种方法

$$\frac{\frac{\begin{array}{ccccccccc}& & & & & & & 9& 9\\ \ast & & & & & & 9& 9& 9\end{array}}{\begin{array}{cccccccc}& & & & & 8& 9& 1\\ & & & & 8& 9& 1& \\ & & & 8& 9& 1& & \end{array}}}{\begin{array}{cccccccccc}& =& & 9& 8& 9& 0& 1& & \end{array}}$$

那么把它转化为代码就简单了，我们同样的：

例如	数字
被减数	99
减数	999

分割字符，因为之前都有步骤，这里我就省略一些不必要的东西了：

···	十万位	万位	千位	百位	十位	个位
被乘数					9	9
*
乘数				9	9	9
步骤1：999中的最后一位的9与被乘数对位相乘结果					81	81
步骤1： 999中的中间位的9与被乘数对位相乘结果				81	81
步骤1： 999中的第一位9与被乘数对位相乘结果			81	81
步骤2： 各结果进位				8	9	1
步骤2： 各结果进位			8	9	1
步骤2.1：			8	17	10	1
步骤2.2： 2.1结果进位			9	8	0	1
步骤2： 各结果进位		8	9	1
步骤2.1：		8	18	9	0	1
步骤2.1：2.1结果进位		9	8	9	0	1
最终结果		9	8	9	0	1

这里大家看着可能会觉得有些乱，我解释一下：
步骤2.1是步骤2后结果的对位相加（第一次步骤2也加了，但是是加到了0上面）
为什么不等乘数所有的位数乘了被乘数后再对位相加和进位呢，举个例子：
$$\begin{array}{cccccccc}& & & & & 8& 9& 1\\ & & & & 8& 9& 1& \\ & & & 8& 9& 1& & \end{array}$$
在这之中，纵向拥有的数字最终都要加到一起，那么如果两个数字长度很大，那么
这个纵向的项数就也会很大，那么使用原来的加法运算也没有意义了，因为可能结
果就回到了长整数相加的问题上。所以我我们每计算两行，就把各列的数字加了，
同时进位，那就把长整数相加的方法用到了这上面。

当然，这样肯定不是最优，因为每算一列就要操作一次有点憨憨,如果有兴趣的话，可以自己优化一下，结合不同的数据类型可以定一个标准，即是最多算几列，再这样操纵一次。
上代码：

# 非负大整数相乘 def MULTI(NUM1, NUM2): # 分割数字字符串 num1 = list(NUM1) num2 = list(NUM2) len1 = len(num1) len2 = len(num2) count = max(len1, len2) temp = [0 for i in range(count*2)] ########例子####### #             999 # *            999 # ----------------- #         81-81-81 #      81-81-81 #   81-81-81 # ------------------ #     9-9-8-0-0-1 ########例子####### for i2 in range(len2-1, -1, -1): # num2中的每位数从个位开始与num1相乘，最后结果按位相加到temp index1 = 0 for i1 in range(len1-1, -1, -1): temp[count*2-(len2-i2)-index1] += int(num2[i2])*int(num1[i1]) index1 += 1 # 每算一次判断进位一次 for i in range(count*2-1, -1, -1): if temp[i] > 9: temp[i-1] += int(temp[i] / 10) temp[i] = temp[i] % 10 # 判断结果是否有0前缀,有则去除 while temp[0] == 0: if len(temp) == 1 and temp[0] == 0: return 0 temp.pop(0) # 返回结果 multi = "" len_t = len(temp) for i in range(len_t): multi += str(temp[i]) return multi 

非负整数相除

这是块难啃的骨头，我研究研究，整理一下~

整数运算

带符号的运算其实很简单，只要不带符号的搞懂了，带符号的只是调用之前的方法再判断需不需要补一个负号即可。
我在这简单解释一下之后的参数，都用的同一组参数：

参数(NUM1：去掉符号后的被加数，NUM2：去掉符号后的加数，Sym1：被加数的符号，Sym2：加数的符号)
NUM类型为str，在传入之前如果前缀带有"-"，则用"0"替换，只替换1次
Sym类型为int，1/-1分别对应"+"/"-"

大整数相加

带符号的加法，其实很简单，只需判断一下符号，调用之前写好的函数就行啦。
由于很简单，直接上代码：

# 大整数相加 def USUM(NUM1, NUM2, Sym1, Sym2): if(Sym1*Sym2 > 0): if Sym1 > 0: return SUM(NUM1, NUM2) else: return "-" + SUM(NUM1, NUM2) else: if Sym1 > 0: return SUB(NUM1, NUM2) else: return SUB(NUM2, NUM1) 

大整数相减

带符号的减法和加法一样：

# 大整数相减 def USUB(NUM1, NUM2, Sym1, Sym2): if(Sym1*Sym2 > 0): if Sym1 > 0: return SUB(NUM1, NUM2) else: return SUB(NUM2, NUM1) else: if Sym1 > 0: return SUM(NUM1, NUM2) else: return "-" + SUM(NUM1, NUM2) 

大整数相乘

带符号的乘法更简单：

def UMULTI(NUM1, NUM2, Sym1, Sym2): if(Sym1*Sym2 > 0): return MULTI(NUM1, NUM2) else: return "-" + MULTI(NUM1, NUM2) 

大整数相除

整理中~

本文地址：https://blog.csdn.net/Chief_Yan/article/details/109025826