基于C++的大整數(shù)類型的設(shè)計與實現(xiàn)

楊正

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

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

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9416（2017）11-0153-01

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

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

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

class big integer

{ protected：

char*base；

int size；int currentPos；

bool is Negative； }

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

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

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

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

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

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

2.3 運算符的重載

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

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

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

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

4 結(jié)語

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

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