楊正

摘要：大整數(shù)類型能夠提供運(yùn)算符重載、四則運(yùn)算在內(nèi)的整套算法。本文針對(duì)基于C++的大整數(shù)類型的設(shè)計(jì)與實(shí)現(xiàn)的研究，將從數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)入手，結(jié)合相關(guān)算法的實(shí)現(xiàn)途徑，對(duì)整數(shù)類型設(shè)計(jì)的應(yīng)用實(shí)例展開論述。

關(guān)鍵詞：C語言；大整數(shù)類型；系統(tǒng)設(shè)計(jì)；運(yùn)算符

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）11-0153-01

對(duì)計(jì)算機(jī)而言，無窮大的數(shù)字范圍需要進(jìn)行一定限制。比如，常見的long型數(shù)據(jù)，其長度若為4個(gè)字節(jié)，其能表示的無符號(hào)數(shù)就為232-1，這樣大的數(shù)字范圍，對(duì)系統(tǒng)測試、天文觀測、科學(xué)計(jì)算等方面的運(yùn)算來說，就有些力不從心。因此，需要通過編程語言的算法設(shè)計(jì)，提供出可行方案。而大整數(shù)算法，就是實(shí)現(xiàn)對(duì)大數(shù)間進(jìn)行運(yùn)算的途徑。因此，加強(qiáng)基于C++的大整數(shù)類型的設(shè)計(jì)與實(shí)現(xiàn)研究具有重要意義。

1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

由于大數(shù)類對(duì)象的基本類型長度不夠，因此數(shù)據(jù)結(jié)構(gòu)內(nèi)部需要采用數(shù)組的形式加以維護(hù)，在此基礎(chǔ)上，還需要定義出bool型數(shù)據(jù)，對(duì)大數(shù)對(duì)象的正負(fù)性質(zhì)進(jìn)行標(biāo)記。經(jīng)規(guī)劃后，大整數(shù)類的基本結(jié)構(gòu)，除了bool標(biāo)記外，還包括int變量數(shù)組以及char數(shù)組。另外，將大整數(shù)類命名為big integer，為節(jié)省空間內(nèi)存，其結(jié)構(gòu)設(shè)計(jì)為：

class big integer

{ protected：

char*base；

int size；int currentPos；

bool is Negative； }

2 相關(guān)算法的實(shí)現(xiàn)

2.1 輸入輸出實(shí)現(xiàn)

大數(shù)類程序的第一步是計(jì)算，第二部就是反饋結(jié)果。或者，實(shí)現(xiàn)數(shù)值的賦予與輸出。輸入輸出實(shí)現(xiàn)中，主要包括兩點(diǎn)：第一是通用的輸入輸出。該過程較為簡單，輸入外部數(shù)組，將數(shù)組中的數(shù)據(jù)進(jìn)行復(fù)制，送到對(duì)象內(nèi)部數(shù)組。輸出就是將內(nèi)部數(shù)組的地址送給外部，對(duì)currentPos等需要設(shè)立相應(yīng)函數(shù)，保證外部對(duì)數(shù)值的獲取。第二是標(biāo)準(zhǔn)輸入輸出，根據(jù)并操作符，對(duì)操作進(jìn)行聲明，遍歷數(shù)組之后，需輸出負(fù)號(hào)。在輸入當(dāng)中，需判定第一個(gè)數(shù)為負(fù)數(shù)后，再開始接收數(shù)據(jù)。然后，對(duì)高位地址的數(shù)組進(jìn)行調(diào)整，保證其以低地址方式保存。

2.2 比較算法實(shí)現(xiàn)

大整數(shù)重載中的相關(guān)運(yùn)算符號(hào)有很多，除了加減以外，還包括大于等于、不等于、小于等于、不等于類符號(hào)。大整數(shù)類具有支持負(fù)數(shù)的特性，因此許多運(yùn)算底層有可能看起來不相符。例如，正負(fù)數(shù)之間的簡單運(yùn)算，很有可能是以減法運(yùn)算為調(diào)用。操作的具體調(diào)用，與大整數(shù)絕對(duì)值大小相關(guān)。因此，需要對(duì)大整數(shù)對(duì)象之間進(jìn)行絕對(duì)值比較。

加法實(shí)現(xiàn)是底層的加法，不可被外部直接訪問，需要被類的其他成員進(jìn)行調(diào)用。將加法實(shí)現(xiàn)函數(shù)進(jìn)行meta-add命名后，無需考慮符號(hào)，其功能是實(shí)現(xiàn)基本加法操作。實(shí)現(xiàn)加法的代碼十分精簡，其主要思想就是利用for循環(huán)及while循環(huán)，實(shí)現(xiàn)逐位相加，然后再進(jìn)行進(jìn)位處理。減法實(shí)現(xiàn)與加法相似，在操作上與加法幾乎一致。首先進(jìn)行初始化，命名meta-sub然后同樣利用for循環(huán)進(jìn)行準(zhǔn)備相減，再利用while循環(huán)實(shí)現(xiàn)出借位處理。乘法實(shí)現(xiàn)屬于指元操作，函數(shù)初始化命名為meta-multi，其實(shí)現(xiàn)思路為，將比較后較小的數(shù)值每一位，逐一與較大的數(shù)值想成，得到n個(gè)結(jié)果后，將其保存在同一個(gè)向量之中。然后，將每個(gè)元素相加就會(huì)得到乘法的最終數(shù)值。

2.3 運(yùn)算符的重載

運(yùn)算符的重載主要包括三方面內(nèi)容：第一，opretor+與opretor+=的實(shí)現(xiàn)，由于元操作無法被外部直接使用，因此需要提供一個(gè)連接內(nèi)外部的端口，而運(yùn)算符的重載就是一個(gè)有效途徑。第二，oprator-和oprator-=的實(shí)現(xiàn)。與加減法相比，這兩個(gè)算法的實(shí)現(xiàn)較為復(fù)雜，但是原理仍然是對(duì)絕對(duì)值大小的判斷。不同的是，加法運(yùn)算需要判斷符號(hào)的異同，而減法需要判斷操作數(shù)值的正負(fù)。第三，oprator*與oprator-/的實(shí)現(xiàn)。與加減法相比，乘法與除法運(yùn)算復(fù)雜程度要大一些，但是在這兩者的運(yùn)算上卻是十分簡單，主需要對(duì)操作數(shù)值的相對(duì)大小進(jìn)行判斷即可，再根據(jù)一定順序，對(duì)乘法運(yùn)算進(jìn)行調(diào)用?；蛘弑容^除數(shù)與被除數(shù)的關(guān)系，若前者較大，程序返回0，否則進(jìn)行下一步操作。

3 大整數(shù)類型設(shè)計(jì)應(yīng)用實(shí)例

在大整數(shù)編程算法當(dāng)中，有一個(gè)簡單而典型的問題，就是“兔子吃胡蘿卜”問題，該問題經(jīng)過改進(jìn)后變?yōu)椋和米拥谝惶斓玫絘根胡蘿卜，吃一部分剩下根。然后，又吃了一根，剩下b根。第二天，兔子繼續(xù)吃，剩下根，在這個(gè)基礎(chǔ)上又多吃一根。到了第十天只剩下一根胡蘿卜，問題是第一天兔子獲得了多少胡蘿卜。

對(duì)待此問題，若利用c++數(shù)據(jù)類型，其中的long和int變量無法表示超出范圍的數(shù)據(jù)，當(dāng)運(yùn)算到第五天，結(jié)果將強(qiáng)制溢出。因此，解決此問題，需要借助大整數(shù)工具，其測試代碼過程大體為：引入自定義大整數(shù)類庫，對(duì)該類型變量進(jìn)行聲明，并賦予初始值為1，利用for循環(huán)語句運(yùn)算，輸出為“第十天有<結(jié)果>根胡蘿卜”，在短時(shí)間內(nèi)，程序就可以完成計(jì)算并給出正確答案。

4 結(jié)語

綜上所述，為了將C語言更好的應(yīng)用在大整數(shù)問題的解決中，本文將基于C++的大整數(shù)類型的設(shè)計(jì)與實(shí)現(xiàn)作為主要研究內(nèi)容，在對(duì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)進(jìn)行分析的基礎(chǔ)上，從輸入輸出實(shí)現(xiàn)、比較算法實(shí)現(xiàn)、不同運(yùn)算實(shí)現(xiàn)、運(yùn)算符的重載等相關(guān)算法方面做出系統(tǒng)探究。研究結(jié)果表明，不同算法組成的C++類庫，不僅能夠應(yīng)用于大整數(shù)實(shí)際問題解決中，還能夠經(jīng)修改后移植到其他操作系統(tǒng)。在未來，還需進(jìn)一步加強(qiáng)對(duì)C++的大整數(shù)類型設(shè)計(jì)與實(shí)現(xiàn)研究，以此為其他語言環(huán)境下大數(shù)運(yùn)算問題的解決提供思路。

Abstract：Large integer types provide a complete set of algorithms for operator overloading and four arithmetic operations. This paper focuses on the design and implementation of large integer types based on C ++. Starting with the design of data structures， this paper discusses the application examples of integer type design in combination with the realization of related algorithms.

Key Words：C language； big integer type； system design； operatorendprint