两个超大整数相加

Archives 趣味题

题面

现有两个非常大的整数，目前所有用来表示数字的类型（指 int，long，float，double）都无法存储，该如何相加？

解法一

• 基本思路

  一个位数为8的整数和一个位数为10的整数，它们相加之和的位数一定是10位；两个10位的整数相加之和的位数最多为11位，也就是说两个整数相加结果的位数最多比较大的那个整数的位数大 1。据此，可以将整数拆分成数段，分段相加。

  假设 int 型整数所能表示的最长的位数为10位，把题目中的加数按每小段 9 位数拆分拆成数段，按高低位顺序分段相加。如果分段相加的结果为10位数，那么说明进位了，将进位的1和相邻的高位分段相加，依次类推。

• 举例说明

整数相加：12340223403234 + 12340823403234
假设整数所能表示的最大位数为 6 位，那么将整数拆分成位数为 5 的整数
【拆分】：12340 22340 3234 + 12340 82340 3234
【按组分段相加】：12340+12340；22340+82340；3234+3234；
【观察结果】：24680（位数为5）；104680（位数为6）；6468（位数为4）；
【进位】：只有中间的那组有6位数，所以需要进位，让第一组的结果再加 1，得到
    24681（位数为5）；04680（位数为5）；6468（位数为4），回到[观察]步骤；
【拼接】：将三组数字转换成字符串，拼接起来。