高精度加法

高精度加法是信息学的一种重要算法。这种算法使用多个存储单位进行计算,因此它的计算范围超过一般使用一个存储单位的算法。也是一些信息学竞赛的常考题目。

基本算法

以358934760892734899+38960302975237462为例:

1、计算结果的位数

358934760892734899共18位

38960302975237462 共17位

故结果不会超过19位。

2、将要计算的数字分割成多段,按照顺序排列(这里以0-32767作为每一存储单位存储的数的限制):

35 8934 7608 9273 4899
3 8960 3029 7523 7462

(为提高空间利用效率,可以一个存储单位存储多位数。)

3、将两数相加。

35 8934 7608 9273 4899
3 8960 3029 7523 7462
和(不进位) 38 17894 10637 16796 12361
和(进位后) 39 7895 0638 6797 2361

4、输出结果。

从高位到低位依次输出。除最高位以外,其他低位上不足4位的要在前面补上0。

参见