Java大整数类的设计及其实现_michael mccloskey

1.1 概述

BigInteger类的开发者是Josh Bloch和Michael McCloskey。

Java大整数类BigInteger继承于Number类并实现了Comparable接口,完全按照面向对象思想构建，因为Java语言没有在C++中编程实现运算符重载的概念，所以Java的BigInteger类是通过提供函数来实现各种大整数运算的。

BigInteger类为所有的Java原始整型操作以及所有在java.lang.Math中的相关方法提供相似的操作.另外BigInteger为求模运算，GCD计算，位操作等提供了运算。

算术运算的语义模仿了定义在Java语言规范中的Java的整型算术运算。比如，如果除数为0就会导致ArithmeticException（算术异常）等等。所有在规范中的溢出都将被忽略，因为BigIntegers将尽量适应运算结果的需要。

移位操作扩展了Java的移位操作，它允许负方向的移位。以负的位距来往右移就相当于往左移位。而无符号的右移运算符（>>>）就省略了。 而按位逻辑操作跟Java的按位操作是相似的。

比较运算执行有符号的整型比较，它跟Java的是相似的。

位逻辑运算操作严密的模仿了Java整型的位运算，二进制运算符(and，or，xor)对二个操作数中较短的那个执行符号扩展，优先于执行(and or xor)操作。

比较操作执行带符号整数比较， 类似于java的相关操作和相等操作的执行。

模数算术运算提供计算余数、执行乘幂等方法。这些方法总是返回一个非零的结果（介于0到modulus-1之间）。

位操作对二元运算的操作数执行单个的bit位操作，如果有必要, 为了操作数能包含指定的位，操作数是扩展了符号的。没有一个单独的位操作能生成一个不同符号的BigInteger，并且BigInteger类提供了无限字长的抽象类,可以确保对前述的每个BigInteger有无限多个“虚符号位”。

对于BigInteger 的所有方法和构造函数,当传递的任何输入参数为空对象引用时就会抛出NullPointerException异常

(其类层次如下图)

java.lang.Object

|
              +--java.lang.Number
|
+--java.math.BigInteger

1.2 BigInteger对大整数的表示

BigInteger类中,事实上使用了int mag[]数组来表示大整数,定义了一个int型变量signum来表示大整数的正负, Signum也是BigInteger的6个构造函数其中一个的参数。signum的有效值-1,0,1分别表示大整数负,零,正。如果signum不是有效值则抛出NumberFormatException异常。为确保对每一个大整数的值都有严密的表示，对大整数的零也要指明signum为0。这意味着BigInteger的零是一个0长度的mag 数组。

BigInteger通过以下6个构造函数来构造和表示大整数:

①BigInteger(byte[] val)

使用一个byte数组表示来构造一个大整数，

例:

byte[] val = new byte[2];

for(int i= 0;i<2;i++)

val[i]=2;

BigInteger firsttest= new BigInteger(vval);

System.out.println("firsttest:"+firsttest);

打印的结果是514,514的二进制表示是10,00000010

②BigInteger(int signum, byte[] magnitude)
用一个byte数组magnitude来构造大整数，用signum的-1，0，1来表示负，零，正。

例:

byte[] magnitude = new byte[2];

for(int i= 0;i<2;i++)

magnitude [i]=1;

BigInteger secondtest= new BigInteger(-1,magnitude);

System.out.println("secondtest:"+secondtest);

打印的结果是-257.

257的二进制是1,00000001

③BigInteger(int bitLength, int certainty, Random rnd)

构造一个随机产生的,正的,指定长度的,可能是素数的大整数,参数certainty指明要进行多少次素数测试.(使用的素数产生方法probablePrime（）下文叙述)

例:

Random rr= new Random();

BigInteger thirdtest= new BigInteger(100,10,rr);

System.out.println("thirdtest:"+thirdtest);

bitLength指的是位长，即是转换为2进制有多少位。

④BigInteger(int numBits, Random rnd)

构造一个随机产生的大整数,范围在0到2^numBits – 1之间.

例:

Random rr = new Random();

BigInteger fourthtest = new BigInteger(100,rr);

System.out.println("fourthtest:"+fourthtest)

numBit指的也是位长。

注意：这个构造函数总是用来产生非负的BigInteger。

⑤BigInteger(String val)

转换十进制的字符串表达方式为BigInteger

这个字符串由一系列的10进制数字和可选择的负号组成

字符转数字的映射由Character.digit实现

这个字符串不能包含任意无关字符(例如：空格)

例:

BigInteger fifthtest = new BigInteger(“12345678901”);

System.out.println(“fifthtest”+fifthtest);

这是最常用的构造函数.

⑥BigInteger(String val, int radix)

转换字符串的表达式为指定(radix)进制的大整数

这个字符串由一系列的指定进制(radix)的数字组成,任意跟上负号

字符转数字的映射由Character.digit实现

同样，这个字符串不能包含任意无关字符(例如：空格)

例:

BigInteger sixthtest = new BigInteger(“FF”,16);

System.out.println(“sixthtest”+sixthtest);

打印结果是255,

当用构造函数构造了BigInteger，就可以非常方便的调用BigInteger的各种方法对BigInteger进行操作，也可以用IO流的print()和println方法直接输出BigInteger.

1.3 BigInteger的四则运算实现

对于BigInteger所有的算术操作，最基本的就是它的四则运算，四则运算也是其它一切运算的构建基础。

add方法和subtract方法实际上进行的是数组对位相加和相减，这个过程用私有的函数来完成，返回的是为此重新分配空间的结果数组索引值（数组首地址）。然后再用结果数组来构造一个BigInteger作为最后的返回值。

multiply方法使用的是数组相乘，用数组来模拟数字相乘，同样使用一个私有的函数来完成这个过程，为相乘结果数组分配新的空间，最后用结果数组来构造一个BigInteger 作为返回值。

和java.lang.String类型一样，BigInteger类也是不变的，所以任何在实例上进行的操作都将生成一个新的实例（创建对象），这个实例的值是操作的结果。所以divide方法实现使用的是MutableBigInteger类，MutableBigInteger类不是公开的，它只供java.math类库内部使用。MutableBigInteger是BigInteger类的另一个版本，它的特点是不创建临时对象的前提上使调用程序得到象BigInteger类型的返回值(称为可变对象技术)。因为大整数的除法是由大量的其他算术操作组成的，所以需要大量的临时对象，而完成大量的操作而不创建新的对象可以极大地改善程序的性能，（因为创建对象的代价是很高的）所以在Java的大整数类中使用MutableBigInteger类中的方法来执行大整数除法。MutableBigInteger类包含在java.math包中，BigInteger类的divide方法使用了MutableBigInteger类的除法运算所返回的结果，使用这个MutableBigInteger类型的结果来构造一个BigInteger。

实际上在MutableBigInteger类中也使用了数组来模拟数字相除。