標準的做法：
typedef struct
{
int *NumHead;//數組頭
int size;//數組大小
}BigNumber;
const int BigBase = 1000000000;//進制
const int PerBitLen = 9;
const int BigSize=sizeof(BigNumber);
//從字符串初始化大數
int BaseChange(char *str,int low,int up)
{
int i=up;
int sum=0;
for(;i>=low;--i)
{
if(str[i]=='0')continue;
if(str[i]<'0'||str[i]>'9')return -1;
sum+=(str[i]-'0')*((int)pow((double)10,(double)up-i));
}
return sum;
}
BigNumber *Str_BigInit(char * str)
{
int strlenth,bitlen;
int i=0,k=0;
BigNumber *Big;
assert(str!=NULL);
while(*str++=='0');
strlenth=strlen(--str);
bitlen=strlenth/PerBitLen;
if(strlenth%PerBitLen!=0)
++bitlen;
Big=(BigNumber *)malloc(BigSize);
Big->NumHead=(int *)malloc(4*(bitlen));
Big->size=bitlen;
assert(Big->NumHead!=NULL);
for(;bitlen>0;--bitlen,strlenth-=PerBitLen)
{
int max= strlenth-1;
int min=strlenth-PerBitLen;
min=min<0?0:min;
Big->NumHead[bitlen-1]=BaseChange(str,min,max);
}
return Big;
}
BigNumber *add(BigNumber *a,BigNumber *b,int offset)//可通過偏移來計算各種加法,O(N)/*偏移針對的是a,即是放大操作，單純的加法offset寫0即可*/
{
int nsize=a->size;
char mark=-1;
BigNumber *result=(BigNumber *)malloc(BigSize);
if(offset==0)
{
if(a->size>b->size)
{
nsize=a->size;
{
BigNumber *newb=(BigNumber *)malloc(BigSize);
newb->NumHead=(int *)malloc(4*nsize);
newb->size=nsize;
memset(newb->NumHead,0,4*(nsize-b->size));
memcpy(newb->NumHead+nsize-b->size,b->NumHead,4*b->size);
b=newb;
}
mark=1;
}
else if(a->size<b->size)
{
nsize=b->size;
{
BigNumber *newa=(BigNumber *)malloc(BigSize);
newa->NumHead=(int *)malloc(4*nsize);
newa->size=nsize;
memset(newa->NumHead,0,4*(nsize-b->size));
memcpy(newa->NumHead+nsize-a->size,a->NumHead,a->size*4);
a=newa;
}
mark=0;
}
}
else
{
if(a->size+offset>b->size)
{
nsize=a->size+offset;
{
BigNumber *newa=(BigNumber *)malloc(BigSize);
BigNumber *newb=(BigNumber *)malloc(BigSize);
newb->NumHead=(int *)malloc(4*nsize);
newb->size=nsize;
memset(newb->NumHead,0,4*(nsize-b->size));
memcpy(newb->NumHead+nsize-b->size,b->NumHead,4*b->size);
b=newb;
newa->NumHead=(int *)malloc(4*nsize);
newa->size=nsize;
memset(newa->NumHead+a->size,0,4*offset);
memcpy(newa->NumHead,a->NumHead,a->size*4);
a=newa;
}
mark=2;
}
else if(a->size+offset<=b->size)
{
nsize=b->size;
{
BigNumber *newa=(BigNumber *)malloc(BigSize);
newa->NumHead=(int *)malloc(4*nsize);
newa->size=nsize;
memset(newa->NumHead,0,4*nsize);
memcpy(newa->NumHead+nsize-a->size-offset,a->NumHead,a->size*4);
a=newa;
}
mark=0;
}
}
result->NumHead=(int *)malloc(4*nsize);
result->size=nsize;
while(--nsize>=0)
result->NumHead[nsize]=a->NumHead[nsize]+b->NumHead[nsize];
if(mark==0)
{
free(a->NumHead);
free(a);
}
else if(mark==1)
{
free(b->NumHead);
free(b);
}
else if(mark==2)
{
free(a->NumHead);
free(b->NumHead);
free(a);
free(b);
}
return result;
}
/////////////////////////////////////////////////////////////////////////////
void BigPrint(BigNumber * result,FILE *fp)
{
int i=0;
assert(result!=NULL&&result->NumHead!=NULL);
while(result->NumHead[i++]==0);
fprintf(fp,"%d",result->NumHead[i++]);
for(;i<result->size;++i)
{
fprintf(fp,"%09d",result->NumHead[i]);
}
fprintf(fp,"\n");
}
int main()
{
BigNumber *a=Str_Init("9999999999999999999999999999999999999999999");
BigNumber *b=Str_Init("123456789876543412351725371253712537152371523");
BigNumber *c=add(a,b,0);
BigPrint(c,stdout);
return 0;
}