【CSDN 编者按】最近大数运算频频出现在面试中,在代码编写的过程中也经常涉及比较大的数的运算,当它们超出程序基本类型所能表示的范围时,就会造成溢出,整形一般的加减乘除已经无法实现了,这时候需要自己写一个程序来实现。
作者 | bigsai 责编 | 欧阳姝黎
前言
各位有过分类刷题的小伙伴,可能看到很多人分类 字符串、贪心、动态规划、bfs、dfs、大数、数论等,初听大数,你可能会差异:大数是个啥?听起来怪高大上的。
这个数字一般用字符串、链表等形式表示、返回,大数运算的核心就是:模拟,模拟我们日常用纸笔算数字的加减乘除流程,然后再根据计算机、编程语言等特性适当存储计算即可,不过,大数除法运算稍微特殊一点,和我们直接模拟的思维方式稍有不同,它就是转换了一下成特殊的加减法运算,后面会细谈。
大数加法
大数加法是最简单的,简单模拟即可。首先,我们想一下两个数加法的流程:从右向左计算求和、进位,一直到最后。
在编程语言中同样也是模拟从右向左逐位相加的过程,不过在具体实现上需要注意一些细节。
枚举字符串将其转换成 char提高效率
从右往左进行计算,可以将结果放到一个数组中最后组成字符串,也可以使用 StringBuider 拼接,拼接的时候最后要逆置一下顺序。
余数每次叠加过需要清零,两数相加如果大于等于 10 即有余数,添加到结果中该位置的数也应该是该数 的结果。
计算完最后还要看看余数是否为1,如果为1需要将其添加到结果,例如 "991" "11"算三个位置为002但还有一个余数需要添加,所以应该是1002。