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

黃明志

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

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

黃明志

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

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

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

0 引言

對于符號整數(shù)，微軟在.NET Framework 3.5中僅能提供表示64位的結(jié)構(gòu)類型，顯然，這樣的整數(shù)可能仍然會因為值范圍過小而不能滿足某類應(yīng)用程序的設(shè)計要求。例如，在搜索引擎這類應(yīng)用程序中，就需要一個比Int64更大的整數(shù)——有符號大整數(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è)計要求

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

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

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

2 實現(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è)計時需要確保Int128結(jié)構(gòu)中公共方法的參數(shù)和返回類型也要符合CLS的要求。這樣，可以在多種語言中讓Int128通過其可用的功能來增強(qiáng)和確保語言的互用性。

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

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

2.2 字段

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

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

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

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

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

2.4 主要方法

（1）CompareTo方法

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

（2）Parse方法

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

2.5 顯式接口

（1）CompareTo顯式接口

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

（2）IConvertible.ToUInt32顯式接口

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

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

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

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

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

（1）相等性

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

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

（2）加法操作

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

（3）++和--

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

（4）移位操作

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

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

通過重載ToString方法來實現(xiàn)。

2.9 哈希代碼

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

3 結(jié)語

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

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

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

[3] Christian Nagel，Bill Evjen，Jay Glynn．C#高級編程（第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-），男，廣東新會人，副教授，研究方向為搜索引擎、計算機(jī)理論與應(yīng)用

2015-01-13

2015-02-13