基于C++的大整數類型的設計與實現

楊正

摘要：大整數類型能夠提供運算符重載、四則運算在內的整套算法。本文針對基于C++的大整數類型的設計與實現的研究，將從數據結構的設計入手，結合相關算法的實現途徑，對整數類型設計的應用實例展開論述。

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

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

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

1 數據結構的設計

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

class big integer

{ protected：

char*base；

int size；int currentPos；

bool is Negative； }

2 相關算法的實現

2.1 輸入輸出實現

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

2.2 比較算法實現

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

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

2.3 運算符的重載

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

3 大整數類型設計應用實例

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

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

4 結語

綜上所述，為了將C語言更好的應用在大整數問題的解決中，本文將基于C++的大整數類型的設計與實現作為主要研究內容，在對數據結構設計進行分析的基礎上，從輸入輸出實現、比較算法實現、不同運算實現、運算符的重載等相關算法方面做出系統(tǒng)探究。研究結果表明，不同算法組成的C++類庫，不僅能夠應用于大整數實際問題解決中，還能夠經修改后移植到其他操作系統(tǒng)。在未來，還需進一步加強對C++的大整數類型設計與實現研究，以此為其他語言環(huá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