128位大整數(shù)的設(shè)計(jì)與實(shí)現(xiàn)

黃明志

（仲愷農(nóng)業(yè)工程學(xué)院信息科學(xué)與技術(shù)學(xué)院，廣州 510225）

128位大整數(shù)的設(shè)計(jì)與實(shí)現(xiàn)

黃明志

（仲愷農(nóng)業(yè)工程學(xué)院信息科學(xué)與技術(shù)學(xué)院，廣州 510225）

某些應(yīng)用程序可能需要使用比Int64更大的整數(shù)，但.NET Framework 3.5并沒(méi)有提供相應(yīng)的結(jié)構(gòu)來(lái)存儲(chǔ)和處理比64位整數(shù)更大的整數(shù)的結(jié)構(gòu)，因此，設(shè)計(jì)大整數(shù)結(jié)構(gòu)顯得非常有必要。根據(jù)CLS規(guī)范，按照.NET Framework 3.5中基本數(shù)據(jù)類型的架構(gòu)，闡述128位有符號(hào)大整數(shù)的設(shè)計(jì)與實(shí)現(xiàn)方法。

大整數(shù)；Int128；.NET Framework

0 引言

對(duì)于符號(hào)整數(shù)，微軟在.NET Framework 3.5中僅能提供表示64位的結(jié)構(gòu)類型，顯然，這樣的整數(shù)可能仍然會(huì)因?yàn)橹捣秶^(guò)小而不能滿足某類應(yīng)用程序的設(shè)計(jì)要求。例如，在搜索引擎這類應(yīng)用程序中，就需要一個(gè)比Int64更大的整數(shù)——有符號(hào)大整數(shù)Int128。Int128值類型能夠表示值介于-170，141，183，460，469，231，731，687，303，715，884，105，728到+170，141，183，460，469，231，731，687，303，715，884，105，727之間的整數(shù)。

1 設(shè)計(jì)要求

首先，Int128結(jié)構(gòu)的設(shè)計(jì)應(yīng)最大限度地符合CLS（Common Language Specification）；其次，為了使Int128結(jié)構(gòu)更易于使用，其設(shè)計(jì)應(yīng)以.NET Framework中的基本數(shù)據(jù)類型如Int32和Int64為范本，提供與Int32和Int64相同或相似的功能對(duì)大整數(shù)進(jìn)行各種運(yùn)算，并使用相同的屬性名和方法名；第三，充分利用C#的運(yùn)算符重載功能，分別實(shí)現(xiàn)+（Add）、-（Subtract）、*（Multiply）①注①★表示顯式接口。、/（Divide）、%（Remainder）、++（Increment）、--（Decrement）、<<（LeftShift）、>>（RightShift）、&（BitwiseAnd）和|（BitwiseOr）等操作。

Int128結(jié)構(gòu)的類圖如圖1所示。

圖1 Int128結(jié)構(gòu)的類圖

2 實(shí)現(xiàn)

要讓Int128符合CLS規(guī)范，首先需將“[assembly: CLS Compliant（true）]”標(biāo)記放在Int128所在裝配件的AssemblyInfo.cs中或Int128.cs文件中，然后將Int128結(jié)構(gòu)標(biāo)記上“[CLSCompliant（true）]”特性：

當(dāng)然，在設(shè)計(jì)時(shí)需要確保Int128結(jié)構(gòu)中公共方法的參數(shù)和返回類型也要符合CLS的要求。這樣，可以在多種語(yǔ)言中讓Int128通過(guò)其可用的功能來(lái)增強(qiáng)和確保語(yǔ)言的互用性。

2.1 數(shù)據(jù)的存儲(chǔ)

為了方便地處理Int128結(jié)構(gòu)所表示的數(shù)，筆者在其結(jié)構(gòu)的內(nèi)部使用了兩個(gè)UInt64私有字段分別存儲(chǔ)和表示Int128的高位和低位。如下所示：

2.2 字段

與Int64等基本數(shù)據(jù)類型一樣，Int128也提供MaxValue和MinValue分別表示此值類型整數(shù)的最大值和最小值，且均為靜態(tài)只讀的。

其中，HiNeg表示負(fù)數(shù)的符號(hào)位，其定義如下：

2.3 構(gòu)造函數(shù)

可以使用.NET Framework中的任一基本數(shù)據(jù)類型實(shí)例化一個(gè)Int128結(jié)構(gòu)。但考慮到C#會(huì)將sbyte、byte、short、ushort、int、uint自動(dòng)隱式轉(zhuǎn)換為long或ulong，因此，實(shí)際設(shè)計(jì)時(shí)其構(gòu)造函數(shù)參數(shù)僅需考慮long、ulong和decimal等少數(shù)基本數(shù)據(jù)類型即可。例如，對(duì)于long，相應(yīng)的構(gòu)造函數(shù)如下：

需要注意的是，在構(gòu)造函數(shù)中，如果參數(shù)為負(fù)數(shù)，必須進(jìn)行特殊的處理。首先，為了簡(jiǎn)化構(gòu)造函數(shù)的邏輯設(shè)計(jì)，負(fù)整數(shù)的實(shí)例化將一律通過(guò)對(duì)相應(yīng)的正整數(shù)進(jìn)行構(gòu)造，然后，加上負(fù)號(hào)；其次，long能夠表示的數(shù)的范圍是-2^64～2^64-1，如果實(shí)參的值為-2^64，則-（value）的值就超出long的范圍而導(dǎo)致上溢錯(cuò)誤，因此，需先對(duì)value進(jìn)行自增操作，然后將其結(jié)果減1。以其他的有符號(hào)的基本數(shù)據(jù)類型進(jìn)行實(shí)例化對(duì)象操作的構(gòu)造函數(shù)均如此處理。最后，對(duì)于不符合CLS的方法，應(yīng)在方法頭前標(biāo)記出不符合CLS的特性。例如，以下公共方法中有不符合CLS的ulong參數(shù)：

2.4 主要方法

（1）CompareTo方法

其功能是比較兩個(gè)128位有符號(hào)整數(shù)并返回對(duì)其相對(duì)值的指示。分別有實(shí)例化方法和靜態(tài)方法。其中，Sign是一個(gè)私有的屬性，表示值是正數(shù)、零或負(fù)數(shù)（1，0，-1）。

（2）Parse方法

通過(guò)Parse靜態(tài)方法，將數(shù)字的字符串表示形式轉(zhuǎn)換為它的等效128位有符號(hào)整數(shù)。

2.5 顯式接口

（1）CompareTo顯式接口

通過(guò)顯式接口實(shí)現(xiàn)IComparable.CompareTo方法：

（2）IConvertible.ToUInt32顯式接口

通過(guò)實(shí)現(xiàn)IConvertible接口中的方法，將引用或值類型的值轉(zhuǎn)換為具有等效值的公共語(yǔ)言運(yùn)行庫(kù)類型。例如：

2.6 負(fù)數(shù)和求負(fù)運(yùn)算

求負(fù)運(yùn)算的實(shí)現(xiàn)如下所示：

其中，Negate方法是求反數(shù)。充分地利用此方法可有效地降低包含負(fù)數(shù)的四則運(yùn)算的處理復(fù)雜度。

2.7 常用運(yùn)算的實(shí)現(xiàn)

（1）相等性

首先，需要重載Equals（object obj）；其次，需要實(shí)現(xiàn)IEquatable中的Equals（Int128 obj）。

同時(shí)，需要重載運(yùn)算符“==”：

（2）加法操作

因?yàn)镮nt128內(nèi)部數(shù)據(jù)分別由ulong類型的_low和_high組成，所以，兩個(gè)大整數(shù)的加法操作只需分別通過(guò)低位和高位相加即可實(shí)現(xiàn)，但要考慮低位相加時(shí)有進(jìn)位時(shí)的特別處理情況：

（3）++和--

通過(guò)重載運(yùn)算符來(lái)實(shí)現(xiàn)。雖然運(yùn)算符重載不在CLS范圍內(nèi)，但符合CLS的代碼設(shè)計(jì)應(yīng)為其提供相應(yīng)的有用名稱及在元數(shù)據(jù)中設(shè)置位的指南。因此，對(duì)于自增運(yùn)算，符合CLS的良好設(shè)計(jì)需要提供名為“Increment”的方法作為運(yùn)算符“++”的友好備用項(xiàng)；而對(duì)于自減運(yùn)算，則需要提供名為“Decrement”的方法作為運(yùn)算符“--”的友好備用項(xiàng)。以下是自增運(yùn)算的實(shí)現(xiàn)：

（4）移位操作

左移位操作通過(guò)重載運(yùn)算符“<<”來(lái)實(shí)現(xiàn)，而右移位操作則通過(guò)重載運(yùn)算符“>>”來(lái)實(shí)現(xiàn)。對(duì)于左移位操作，符合CLS的良好設(shè)計(jì)需要提供名為“LeftShift”的方法作為運(yùn)算符“<<”的友好備用項(xiàng)；提供名為“Right-Shift”的方法作為運(yùn)算符“>>”的友好備用項(xiàng)。

2.8 數(shù)據(jù)的顯示

通過(guò)重載ToString方法來(lái)實(shí)現(xiàn)。

2.9 哈希代碼

根據(jù).NET Framework文檔的要求，重寫Equals方法也應(yīng)該重寫GetHashCode方法。以下是獲取實(shí)例的哈希代碼的實(shí)現(xiàn)：

3 結(jié)語(yǔ)

設(shè)計(jì)一個(gè)架構(gòu)良好的Int128結(jié)構(gòu)并非易事，需要提供與Int64等基本數(shù)據(jù)類型相同的用戶使用體驗(yàn)，其設(shè)計(jì)需要對(duì).NET Framework體系結(jié)構(gòu)具有深刻而透徹的理解。本文雖然僅提供了Int128的實(shí)現(xiàn)，但使用同樣的方法，相信讀者可以方便地設(shè)計(jì)出UInt128、Int256和UInt256等結(jié)構(gòu)類型以滿足各類應(yīng)用程序的實(shí)際要求。

[1] 李曉明，閆宏飛，王繼民著．搜索引擎[M]．北京：科學(xué)出版社，2005

[2] Mickey Williams著．Visual C#.NET技術(shù)內(nèi)幕[M]．冉曉旻，羅鄧，郭炎譯．北京：清華大學(xué)出版社，2003

[3] Christian Nagel，Bill Evjen，Jay Glynn．C#高級(jí)編程（第4版）[M]．李敏波譯．北京：清華大學(xué)出版社，2006

Design and Implementation of 128-bit Big Integer

HUANG Ming-zhi
（College of Information Science and Technology，ZhongkaiUniversity of Agriculture and Engineering，Guangzhou 510225）

Some applicationsmay require the use of integers larger than Int64，but.NET Framework 3.5 does not provide the appropriate structure for storing and processing of integers larger than 64-bit，so designing the structure of big integer is very necessary.According to the CLS specification and in accordancewith the.NET Framework 3.5 base data type in the schema,and describes the design and implementation of 128-bit signed big integer.

Big Integer;Int128;.NET Framework

1007-1423（2015）07-0040-05

10.3969/j.issn.1007-1423.2015.07.012

黃明志（1964-），男，廣東新會(huì)人，副教授，研究方向?yàn)樗阉饕妗⒂?jì)算機(jī)理論與應(yīng)用

2015-01-13

2015-02-13