目錄

大整數的存儲

大整數的四則運算

高精度加法

高精度減法

高精度與低精度的乘法

高精度與低精度的除法?

大整數的存儲

對于大整數使用數組存儲，例如定義int型數組d[1000]，那么這個數組中的每一位就代表了存放的整數的每一位。如將整數235813存儲到數組中，則有d[0]=3,d[1]=1,d[2]=8,d[3]=5,d[4]=3,d[5]=2,即整數的高位存儲在數組的高位，整數的低位存儲在數組的低位。不反過來存儲的原因是，在進行運算的時候都是從整數低位到高位進行枚舉，順位存儲和這種思維相和。但是也會由此產生一個需要注意的問題：把整數按照字符串%s讀入的時候，實際上是逆位存儲的，即str[0]='2',str[1]='3',……,str[5]='3'，因此在讀入之后需要在另存為d[]數組的時候反轉一下。

而為了方便隨時獲取大整數的長度，一般都會定義一個int型變量len來記錄其長度，并和d數組組合成結構體。

struct bign{int d[1000];int len;
};

顯然，在定義結構體變量之后，需要馬上初始化結構體，為了減少在實際輸入代碼時總是忘記初始化的問題，在結構體內部加上以下代碼：

	bign(){memset(d,0,sizeof(d));len=0;}

因此大整數結構體就變成了這樣：

struct bign{int d[1000];int len;bign(){memset(d,0,sizeof(d));len=0;}
};

這樣在每次定義結構體變量時，都會自動對該變量進行初始化。

而輸入大整數時，一般都是先用字符串讀入，然后再把字符串另存為bign結構體。由于使用char數組進行讀入時，整數的高位會變成數組的低位，而整數的低位會變成數組的高位，因此為了讓整數在bign中是順序存儲，需要讓字符串倒著賦給d[]數組。

bign change(char str[]){bign a;a.len=strlen(str);for(int i=0;i<a.len;i++){a.d[i]=str[a.len-i-1]-'0';}return 0;
}

如果要比較兩個bign變量的大小，規則也很簡單：先判斷兩者的 len大小，如果不相等，則以長的為大；如果相等，則從高位到低位進行比較，直到出現某一位不等，就可以判斷兩個數的大小。具體代碼如下：

int compare(bign a,bign b){if(a.len>b.len){return 1;//a大 }else if(a.len<b.len){return -1;//b大 }else{for(int i=a.len-1;i>=0;i--){if(a.d[i]>b.d[i]){return 1;}else if(a.d[i]<b.d[i]){return -1;}}return 0;//兩數相等 }
}

接下來主要介紹四個運算：（1）高精度加法；（2）高精度減法；（3）高精度與低精度的乘法；（4）高精度與低精度的除法。

大整數的四則運算

高精度加法

將改為上的兩個數字和進位相加，得到的結果取個位數作為該位結果，取十位數作為新的進位。

bign add(bign a,bign b){bign c;int carry=0;//進位for(int i=0;i<a.len||i<b.len;i++){int temp=a.d[i]+b.d[i]+carry;c.d[c.len++]=temp%10;carry=temp/10;} if(carry!=0){c.d[c.len++]=carry;}return 0;
}

下面是完整的A+B的代碼。

#include<stdio.h>
#include<string.h>
struct bign{int d[1000];int len;bign(){memset(d,0,sizeof(d));len=0;}
};
bign change(char str[]){bign a;a.len=strlen(str);for(int i=0;i<a.len;i++){a.d[i]=str[a.len-i-1]-'0';}return a;
}
bign add(bign a,bign b){bign c;int carry=0;for(int i=0;i<a.len||i<b.len;i++){int temp=a.d[i]+b.d[i]+carry;c.d[c.len++]=temp%10;carry=temp/10;}if(carry!=0){c.d[c.len++]=carry;}return c;
}
void print(bign a){for(int i=a.len-1;i>=0;i--){printf("%d",a.d[i]);}
}
int main(){char str1[1000],str2[1000];scanf("%s%s",str1,str2);bign a=change(str1);bign b=change(str2);print(add(a,b));return 0;
}

最后指出，這樣寫法的條件是兩個對象都是非負整數。如果有一方是負的，可以在轉換到數組這一步時去掉其負號，然后采用高精度減法；如果兩者都是負的，就都去掉負號后用高精度加法，最后把負號再加回去即可。

高精度減法

對某一步，比較被減位和減位，如果不夠減，則令被減位的高位減1， 被減位加10再進行減法；如果夠減，則直接減。最后一步要注意減法后高位可能有多余的0，要忽視它們，但也要保證結果至少有一位數。

bign sub(bign a,bign b){bign  c;for(int i=0;i<a.len||i<b.len;i++){if(a.d[i]<b.d[i]){a.d[i+1]--;a.d[i]+=10;}c.d[c.len++]=a.d[i]-b.d[i];}while(c.len-1>=1&&c.d[c.len-1]==0){c.len--;}return c;
}

高精度減法的完整代碼即為把上面的sub函數替代高精度加法中add函數的位置即可，記得 調用的時候也是用sub函數。

高精度與低精度的乘法

取bign的某位與int型整體相乘，再與進位相加，所得結果的個位數作為該位結果，高位部分作為新的進位。

bign multi(bign a,int b){bign c;int carry=0;for(int i=0;i<a.len;i++){int temp=a.d[i]*b+carry;c.d[c.len++]=temp%10;carry=temp/10;}while(carry!=0){c.d[c.len++]=carry%10;carry/=10;}return c;
}

完整的A*B的代碼只需要把高精度加法中的add函數改成這里的multi函數，并注意輸入的時候b是作為int型輸入即可。

高精度與低精度的除法?

上一步的余數乘以10加上該步的位，得到該步臨時的被除數，將其與除數比較：如果不夠除，則該位的商為0；如果夠除，則商即為對應的商，余數即為對應的余數。最后一位要注意減法后高位可能有多余的0，要忽視它們，但也要保證結果至少有一位數。

bign divide(bign a,int b,int& r){bign c;c.len=a.len;for(int i=a.len-1;i>=0;i--){r=r*10+a.d[i];if(r<b){c.d[i]=0;}else{c.d[i]=r/b;r=r%b;}}while(c.len-1>=1&&c.d[c.len-1]==0){c.len--;}return c;
}

在上述代碼中，考慮到函數每次只能返回一個數據，而很多題目里面會經常要求得到余數，因此把余數寫成引用的形式直接作為參數傳入，或是把r設成全局變量。