概述

大数加法的核心思想是，将待求解的两个整数转换为两个动态数组(切片)的形式，然后对数组的每个位进行相加，得到一个和数组，最后将和数组整理成符合10进制的数组。 以下面以大整数$SS$和$TT$相加为例进行说明：其中，$SS$可以表示为一个数组$S=s_{n-1}\cdots s_{0}S=s\_\{n-1\}\backslash cdots\; s\_\{0\}$, $TT$也可以表示一个数组$T=t_{l-1}\cdots t_{0}T=t\_\{l-1\}\backslash cdots\; t\_\{0\}$。

首先，按照将$SS$和$TT$转换为逆存的整型数组，$S^{\mathrm{\prime }}=s_0{s}_1\cdots s_{n-1}S\text{'}=s\_\{0\}s\_\{1\}\backslash cdots\; s\_\{n-1\}$和整型数组$T^{\mathrm{\prime }}=t_0{t}_1\cdots t_{l-1}T\text{'}=t\_\{0\}t\_\{1\}\backslash cdots\; t\_\{l-1\}$。例如：$S=100S=100$转换成$S^{\mathrm{\prime }}=001S\text{'}=001$。这样做的主要目的是为了方便后续实现基于数组的大整数加法运算。

其次，比较$S^{\mathrm{\prime }}S\text{'}$和$T^{\mathrm{\prime }}T\text{'}$的的数组长度，并选择长度长的数组作为结果数据存储数组，这里假设$S^{\mathrm{\prime }}S\text{'}$的长度$nn$大于$T^{\mathrm{\prime }}T\text{'}$的长度$ll$,于是选择$S^{\mathrm{\prime }}S\text{'}$作为存储结果的数组，及每个数组位$ii$运算为$S^{\mathrm{\prime }}[i]=S^{\mathrm{\prime }}[i]+T^{\mathrm{\prime }}[i]S\text{'}[i]=S\text{'}[i]+T\text{'}[i]$,()。

接着，对计算的结果数组$S^{\mathrm{\prime }}S\text{'}$进行相应的进为处理，即判定是否成立，如果不成立则不改变第$ii$位的值$S^{\mathrm{\prime }}[i]S\text{'}[i]$；否则，将$S^{\mathrm{\prime }}[i]S\text{'}[i]$除以 10的余数作为$S^{\mathrm{\prime }}[i]S\text{'}[i]$的值，而$S^{\mathrm{\prime }}[i]\mathrm{/}10+S^{\mathrm{\prime }}[i+1]S\text{'}[i]/10+S\text{'}[i+1]$作为第$i+1i+1$的新值。

最后，逆转数组$S^{\mathrm{\prime }}S\text{'}$做输出结果。

例子：

最高位不进位的情况：如$S=103S=103$,$T=99T=99$,那么此时，数组$S^{\mathrm{\prime }}=[3,0,1]S\text{'}=[3,0,1]$,$T^{\mathrm{\prime }}=[9,9]T\text{'}=[9,9]$。由于此时，$S^{\mathrm{\prime }}S\text{'}$的长度为3大于$T^{\mathrm{\prime }}T\text{'}$的长度2，于是选择$S^{\mathrm{\prime }}S\text{'}$作为结果存储数组，即$S^{\mathrm{\prime }}[i]=S^{\mathrm{\prime }}[i]+T^{\mathrm{\prime }}[i]S\text{'}[i]=S\text{'}[i]+T\text{'}[i]$,且初始计算得$S^{\mathrm{\prime }}=[12,9,1]S\text{'}=[12,9,1]$。然后处理数组$S^{\mathrm{\prime }}S\text{'}$如下：

$S^{\mathrm{\prime }}[0]=[2]S\text{'}[0]=[2]$,$S^{\mathrm{\prime }}[1]=10S\text{'}[1]=10$ $S^{\mathrm{\prime }}[0]=[2]S\text{'}[0]=[2]$,$S^{\mathrm{\prime }}[1]=0S\text{'}[1]=0$,$S^{\mathrm{\prime }}[2]=2S\text{'}[2]=2$

于是此时，$S^{\mathrm{\prime }}=[2,0,2]S\text{'}=[2,0,2]$,逆转后得输出结果为202。

最高位进位的情况：如$S=103S=103$,$T=908T=908$,那么此时，数组$S^{\mathrm{\prime }}=[3,0,1]S\text{'}=[3,0,1]$,$T^{\mathrm{\prime }}=[8,0,9]T\text{'}=[8,0,9]$。由于此时，$S^{\mathrm{\prime }}S\text{'}$的长度为3等于$T^{\mathrm{\prime }}T\text{'}$的长度3，可任意选择$S^{\mathrm{\prime }}S\text{'}$或者$T^{\mathrm{\prime }}T\text{'}$作为结果存储数组，这里选择$S^{\mathrm{\prime }}S\text{'}$作为结果存储数组。即$S^{\mathrm{\prime }}[i]=S^{\mathrm{\prime }}[i]+T^{\mathrm{\prime }}[i]S\text{'}[i]=S\text{'}[i]+T\text{'}[i]$,且初始计算得$S^{\mathrm{\prime }}=[11,0,10]S\text{'}=[11,0,10]$；然后处理数组$S^{\mathrm{\prime }}S\text{'}$如下：

$S^{\mathrm{\prime }}[0]=[1]S\text{'}[0]=[1]$,$S^{\mathrm{\prime }}[1]=1S\text{'}[1]=1$ $S^{\mathrm{\prime }}[0]=[1]S\text{'}[0]=[1]$,$S^{\mathrm{\prime }}[1]=1S\text{'}[1]=1$,$S^{\mathrm{\prime }}[2]=0S\text{'}[2]=0$,$S^{\mathrm{\prime }}[3]=1S\text{'}[3]=1$

于是此时，$S^{\mathrm{\prime }}=[1,1,0,1]S\text{'}=[1,1,0,1]$,逆转后得输出结果为1011。值得注意的是，最初数组$S^{\mathrm{\prime }}S\text{'}$的长度为3，为了存储$S^{\mathrm{\prime }}[3]S\text{'}[3]$,需要在考虑最高位进位的情况时，先对原始数组$S^{\mathrm{\prime }}S\text{'}$进行扩容。

基于Go语言的代码实现

func Plus(s,t string) string{
    s1:=Convtoarray(s)
    s2:=Convtoarray(t)
    max,min:=maxlenarray(&s1,&s2)
    for i:=0;i<len(*min);i++{
        (*max)[i]=(*max)[i]+(*min)[i]
    }
    for i:=0;i<len(*max);i++{
        if (*max)[i]>=10 && i<len(*max)-1{
            h:=(*max)[i]
            (*max)[i]=h%10
            (*max)[i+1]=h/10+(*max)[i+1]
        }else if i==len(*max)-1 && (*max)[i]>=10{
            h:=(*max)[i]
            (*max)[i]=h%10
            (*max)=append(*max,h/10)
        }
    }
    return Reconstruct(*max)
}
 
func maxlenarray(s1,s2 *[]int) (*[]int,*[]int){
    if len(*s1)>len(*s2){
        return s1,s2
    }
    return s2,s1
}
 
 
func Convtoarray(s string) []int{
    a:=[]byte(s)
    var arr []int
    for i:=len(a)-1;i>=0;i--{
        arr=append(arr,int(a[i])-48)
    }
    return arr
}
 
func Reconstruct(arr []int) string{
    var str []byte
    for i:=len(arr)-1;i>=0;i--{
        str=append(str,byte(arr[i]+48))
    }
    return string(str)
}