128位大整数的设计与实现

黄明志

（仲恺农业工程学院信息科学与技术学院，广州 510225）

128位大整数的设计与实现

黄明志

（仲恺农业工程学院信息科学与技术学院，广州 510225）

某些应用程序可能需要使用比Int64更大的整数，但.NET Framework 3.5并没有提供相应的结构来存储和处理比64位整数更大的整数的结构，因此，设计大整数结构显得非常有必要。根据CLS规范，按照.NET Framework 3.5中基本数据类型的架构，阐述128位有符号大整数的设计与实现方法。

大整数；Int128；.NET Framework

0 引言

对于符号整数，微软在.NET Framework 3.5中仅能提供表示64位的结构类型，显然，这样的整数可能仍然会因为值范围过小而不能满足某类应用程序的设计要求。例如，在搜索引擎这类应用程序中，就需要一个比Int64更大的整数——有符号大整数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之间的整数。

1 设计要求

首先，Int128结构的设计应最大限度地符合CLS（Common Language Specification）；其次，为了使Int128结构更易于使用，其设计应以.NET Framework中的基本数据类型如Int32和Int64为范本，提供与Int32和Int64相同或相似的功能对大整数进行各种运算，并使用相同的属性名和方法名；第三，充分利用C#的运算符重载功能，分别实现+（Add）、-（Subtract）、*（Multiply）①注①★表示显式接口。、/（Divide）、%（Remainder）、++（Increment）、--（Decrement）、<<（LeftShift）、>>（RightShift）、&（BitwiseAnd）和|（BitwiseOr）等操作。

Int128结构的类图如图1所示。

图1 Int128结构的类图

2 实现

要让Int128符合CLS规范，首先需将“[assembly: CLS Compliant（true）]”标记放在Int128所在装配件的AssemblyInfo.cs中或Int128.cs文件中，然后将Int128结构标记上“[CLSCompliant（true）]”特性：

当然，在设计时需要确保Int128结构中公共方法的参数和返回类型也要符合CLS的要求。这样，可以在多种语言中让Int128通过其可用的功能来增强和确保语言的互用性。

2.1 数据的存储

为了方便地处理Int128结构所表示的数，笔者在其结构的内部使用了两个UInt64私有字段分别存储和表示Int128的高位和低位。如下所示：

2.2 字段

与Int64等基本数据类型一样，Int128也提供MaxValue和MinValue分别表示此值类型整数的最大值和最小值，且均为静态只读的。

其中，HiNeg表示负数的符号位，其定义如下：

2.3 构造函数

可以使用.NET Framework中的任一基本数据类型实例化一个Int128结构。但考虑到C#会将sbyte、byte、short、ushort、int、uint自动隐式转换为long或ulong，因此，实际设计时其构造函数参数仅需考虑long、ulong和decimal等少数基本数据类型即可。例如，对于long，相应的构造函数如下：

需要注意的是，在构造函数中，如果参数为负数，必须进行特殊的处理。首先，为了简化构造函数的逻辑设计，负整数的实例化将一律通过对相应的正整数进行构造，然后，加上负号；其次，long能够表示的数的范围是-2^64～2^64-1，如果实参的值为-2^64，则-（value）的值就超出long的范围而导致上溢错误，因此，需先对value进行自增操作，然后将其结果减1。以其他的有符号的基本数据类型进行实例化对象操作的构造函数均如此处理。最后，对于不符合CLS的方法，应在方法头前标记出不符合CLS的特性。例如，以下公共方法中有不符合CLS的ulong参数：

2.4 主要方法

（1）CompareTo方法

其功能是比较两个128位有符号整数并返回对其相对值的指示。分别有实例化方法和静态方法。其中，Sign是一个私有的属性，表示值是正数、零或负数（1，0，-1）。

（2）Parse方法

通过Parse静态方法，将数字的字符串表示形式转换为它的等效128位有符号整数。

2.5 显式接口

（1）CompareTo显式接口

通过显式接口实现IComparable.CompareTo方法：

（2）IConvertible.ToUInt32显式接口

通过实现IConvertible接口中的方法，将引用或值类型的值转换为具有等效值的公共语言运行库类型。例如：

2.6 负数和求负运算

求负运算的实现如下所示：

其中，Negate方法是求反数。充分地利用此方法可有效地降低包含负数的四则运算的处理复杂度。

2.7 常用运算的实现

（1）相等性

首先，需要重载Equals（object obj）；其次，需要实现IEquatable中的Equals（Int128 obj）。

同时，需要重载运算符“==”：

（2）加法操作

因为Int128内部数据分别由ulong类型的_low和_high组成，所以，两个大整数的加法操作只需分别通过低位和高位相加即可实现，但要考虑低位相加时有进位时的特别处理情况：

（3）++和--

通过重载运算符来实现。虽然运算符重载不在CLS范围内，但符合CLS的代码设计应为其提供相应的有用名称及在元数据中设置位的指南。因此，对于自增运算，符合CLS的良好设计需要提供名为“Increment”的方法作为运算符“++”的友好备用项；而对于自减运算，则需要提供名为“Decrement”的方法作为运算符“--”的友好备用项。以下是自增运算的实现：

（4）移位操作

左移位操作通过重载运算符“<<”来实现，而右移位操作则通过重载运算符“>>”来实现。对于左移位操作，符合CLS的良好设计需要提供名为“LeftShift”的方法作为运算符“<<”的友好备用项；提供名为“Right-Shift”的方法作为运算符“>>”的友好备用项。

2.8 数据的显示

通过重载ToString方法来实现。

2.9 哈希代码

根据.NET Framework文档的要求，重写Equals方法也应该重写GetHashCode方法。以下是获取实例的哈希代码的实现：

3 结语

设计一个架构良好的Int128结构并非易事，需要提供与Int64等基本数据类型相同的用户使用体验，其设计需要对.NET Framework体系结构具有深刻而透彻的理解。本文虽然仅提供了Int128的实现，但使用同样的方法，相信读者可以方便地设计出UInt128、Int256和UInt256等结构类型以满足各类应用程序的实际要求。

[1] 李晓明，闫宏飞，王继民著．搜索引擎[M]．北京：科学出版社，2005

[2] Mickey Williams著．Visual C#.NET技术内幕[M]．冉晓旻，罗邓，郭炎译．北京：清华大学出版社，2003

[3] Christian Nagel，Bill Evjen，Jay Glynn．C#高级编程（第4版）[M]．李敏波译．北京：清华大学出版社，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-），男，广东新会人，副教授，研究方向为搜索引擎、计算机理论与应用

2015-01-13

2015-02-13