昨天在讲算法的时候， 突然提到超大数。今天就讲一下BigInteger。 在java 中，基本类型表达的最大数就是long 类型了， 它是8个字节，整数表示范围是：-(2的63次方) ~ (2的63次方) 减 -1。
正常情况下一个整数最多只能放在long类型之中，但是如果现在有如下的一个数字：
1111111111111111111111111111111111111111111111111
根本就是无法保存的，所以为了解决这样的问题，在java中引入了两个大数的操作类：
操作整型：BigInteger
操作小数：BigDecimal
当然了，这些大数都会以字符串的形式传入。因此java有了BigInteger.
一个问题， 为啥没有BigLong ，而是BigInteger？ 大家看看下面的分析看看自己能不能找到答案。
什么是BigInteger（定义）
BigInteger类的基本结构如下所示：
image.png
BigInteger已实现的接口：Serializable, Comparable
类定义如下：
BigInteger是不可变的任意精度的整数。所有操作中，都以二进制补码形式表示 BigInteger（如 Java 的基本整数类型）。BigInteger 提供所有 Java 的基本整数操作符的对应物，并提供 java.lang.Math 的所有相关方法。另外，BigInteger 还提供以下运算：模算术、GCD 计算、质数测试、素数生成、位操作以及一些其他操作。
属性
下面看看BigInteger有哪些重点的属性，主要的有下面两个：
- final int signum
signum属性是为了区分：正负数和0的标志位，整数用1表示，负数用-1表示，零用0表示。 - final int[] mag
mag是magnitude的缩写形式，mag数组是存储BigInteger数值大小的，采用big-endian的顺序，也就是高位字节存入低地址，低位字节存入高地址，依次排列的方式。
BigInteger存储大数的方式就是将数字存储在一个整型的数组中，这样就能解决可以存很多很多位数字的问题。那么，只用一个整型数组的话，如何表示一个整数的正负呢？那么就需要有一个单独的成员变量来标明该数的正负。
构造函数
public BigInteger(byte[] val) {
if (val.length == 0)
throw new NumberFormatException("Zero length BigInteger");
if (val[0] < 0) {
mag = makePositive(val); //这个函数的作用是将负数的byte字节数组转换为正值。
signum = -1; //如果数组第一个值为负数，则将数组变正存入mag，signum赋-1
} else {
mag = stripLeadingZeroBytes(val);//如果非负，则可直接去掉前面无效零，再赋给mag
signum = (mag.length == 0 ? 0 : 1);
}
}
将包含 BigInteger 的二进制补码表示形式的 byte 数组转换为 BigInteger。输入数组假定为 big-endian 字节顺序：最高有效字节在第零个元素中。
再来看另外一种构造BigInteger的方式:public BigInteger(String val) 这个构造函数接收一个字符串，然后直接将字符串转换成BigInteger类型。
public static void main(String[] args) {
BigInteger bigInteger = new BigInteger("123456789987654321123456789987654321123456789987654321");
System.out.println(bigInteger);
}
这看起来很方便，只要我们明确的知道我们想要的数字的字符串形式，就可以直接用他构造一个BigInteger
接着，我们就分析一下这个函数是怎么实现的，难道只是把我们传入的字符串直接存到mag数组里面了么？以下是该构造函数的实现：
public BigInteger(String val) {
this(val, 10);
}
这个函数调用了另外一个构造方法，那么我们就直接分析这个构造方法： public BigInteger(String val, int radix)
该构造函数就是把一个字符串val所代表的的大整数转换并保存mag数组中,并且val所代表的字符串可以是不同的进制(radix决定)，比如，我们这样构造一个BigInteger：BigInteger bigInteger = new BigInteger("101",2);，那么我们得到的结果就是5。
分析该构造函数源码之前,先想一个问题,构造一个大整数开始最主要的问题是如何把一个大数保存到mag数组中,通常我们自己实现的话很有可能是数组每块存一位数（假设大数为10进制）,但这样的话想想也知道太浪费空间,因为一个int值可以保存远不止一位十进制数. Java语言里每个int值大小范围是-2^31至2^31-1 即-2147483648~2147483647,因此一个int值最多可保存一个10位十进制的整数,但是为了防止超出范围(2222222222这样的数int已经无法存储),保险的方式就是每个int保存9位的十进制整数.JDK里的mag数组即是这样的保存方式. 因此若一串数为：18927348347389543834934878. 划分之后就为：18927348 | 347389543 | 834934878. mag[0]保存18927348 ,mag[1]保存347389543 ,mag[2]保存834934878 这样划分可以最大利用每一个int值,使得mag数组占用更小的空间.当然这只是第一步.
划分的问题还没有说完，上述构造函数能够支持不同进制的数,最终转换到mag数组里面的数都是十进制,那么不同进制的大数,每次选择划分的位数就不相同，若是2进制,每次就可以选择30位来存储到一个int数中(int值大小范围是-231至231-1)，若是3进制319<2147483647<320,因此每次就可以选择19位来存储到一个int数中,对于不同进制每次选择的位数不同,因此需要有一个数组来保存不同进制应当选择的位数,于是就有：
private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
该数组保存了java支持的最大至最小进制所对应的每次划分的位数
该构造方法里还包含了一个相关的数组bitsPerDigit,该数组用于计算初始化mag数组的大小.
private static long bitsPerDigit[] = { 0, 0,
1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
5253, 5295};
“bitsPerDigit是用于计算radix进制m个有效数字 转换成2进制所需bit位[假设所需x位],我们来看一个计算式:radix^m – 1 = 2^x – 1, 解这个方程得 x = m * log2(radix) , 现在m是几位有效数字,常量就只有 log2(radix),这是一个小数,这不是我们喜欢的,所以我们希望用一个整数来表示,于是我们把他扩大1024倍然后取整,例如3进制
bitsPerDigit[3][3] = 1624(我用计算器算了一下 x = log2(3) * 1024 ~= 1623.xxx) ,我们队这个数取整,为什么取1624呢,其实只要不超过太多都可以的,你可以设置为1620,1600,1610…;”
也就是说对于一串数(N进制),其转换成二进制的位数再乘以1024就是bitsPerDigit数组里面对应的数据,乘以1024再取整可能让人看着舒服吧.
算法基础
int能够支撑的数据长度以及基数
我们知道，存储实际数据的是int数组
int表示范围是:
-231 ~ 231-1 也就是 -2147483648 ~ 2147483647
- 对于十进制,可以表示10位十进制数字
但是 2147483648 (2147483647+1) 仍旧是10位数字却溢出了,所以选择保存9位十进制数
所以每个int 十进制下最大值为10的9次方
image.png
-
对于二进制
最大值 231-1 ，所以只能保存30位 2进制数 -
对于三进制
319 =1162261467 <2147483647<320 = 3486784401
所以能够保存19位 三进制数,所以每个int 三进制下最大值为3的19次方
image.png
-
对于十六进制
167 =268435456 < < 2147483647 < 168 = 4294967296
所以能够保存7位十六进制数
image.png
所以就有了这么两个映射数组
- digitsPerInt
表示每个int 可以表示的，指定进制下数字的位数，下标索引就是进制基数
比如可以表示十六进制的位数为digitsPerInt[16] = 7 -
intRadix
表示每个int可以表示的指定进制下的最大值，下标索引就是进制基数
比如 每一位int 可以表示的十进制的最大值为 intRadix[10] = 0x3b9aca00=1，000，000，000
image.png
其实intRadix这个数就是:
BigInteger在这个基数下的基数
这句话有点绕，BigInteger内部是数组，假如为mag[0] mag[1] intRadix[10] = 0x3b9aca00
那么也就是，BigInteger在十进制，也就是10为基数下的基数为0x3b9aca00
那么这个值就是 mag[0] x 0x3b9aca001 + mag[1] x 0x3b9aca000
就如同十进制的数12的计算方式为1x101 + 2 x100 =12 一样的道理
同理它内部也有两个针对Long 的数组，用于内部计算使用
BigInteger内部使用int数组表示
普通数值使用每个数值位上的数字进行表示
一个BigInteger有多个int
一个普通数值有多个数字位
每个int能够表示的指定进制的最大值--intRadix 中保存的数据
其实 就是 BigInteger 的基于每个int作为一个元素的进制基数
image.png
位数表示
假设R为指定的基数 ，L为指定基数的数字的长度 那么用多少位2进制数可以表示?
image.png
L位R进制的数能够表示的最大值为
image.png
比如R=10 L=2 也就是十进制两位数能够表示的最大值为: 10的平方减1 等于 99
image.png
解上面的方程，可以得出来
x的长度为 ：L 乘以以2为底R的对数
bitsPerDigit 就是每个数字需要的比特位数乘以1024后在取整
之所以乘以1024然后在取整
应该是为了简化运算，这个数必然要是2的N次方，计算机移位最快
当然，这个地方乘以1024 实际使用的时候必然也还得除以1024
image.png
以2为底 2的对数 = 1 * 1024 = 1024
以2为底 3的对数 = 1.5849625007 * 1024 = 1623.0016007168 -> 1624
以2为底 4的对数 = 2 * 1024 = 2048
以2为底 5的对数 = 2.3219280949 * 1024 = 2377.6543691776 ->2378
以2为底 10的对数 = 3.3219280949 * 1024=3401.6543691776 -> 3402
以2为底 16的对数 = 4 * 1024 = 4096
说到这，我们再回头看看上面介绍的几个数组
- digitsPerInt 表示不同基数(进制)下一个int 能够表示的数字的长度 ，这个位数其实就是按照多长进行分割组装
- intRadix 就是基数
- bitsPerDigit 是用来推算需要多少个int的，也就是int数组的长度
以上是String构造BigInteger的用到的一些基本概念
构造整数
我们以一个最简单的例子进行演示:
- 计算字符串 "123" 十进制表示的数值
- 使用数组mag 来进行存储每一位数字
- 显然需要mag[3] 不要纠结mag类型，此处只是为了示例
- 找到第一个字符 "1" ，转换为数字1， 然后保存到mag[3] = 1 (我们此处假定从数组最后开始存放)
- 找到第二个字符 "2" ， 转换为数字2，然后 计算 mag[3] x 10 +2
mag[3] x 10 = 10 ，结果进行保存
mag[2] 保存1 mag[3] 保存0
然后再加上2 0+2 = 2 不用进位
所以最终结果为mag[3] = 2 mag[2] = 1 -
找到第三个字符 "3" ， 转换为数字3，然后 计算 (mag[2]mag[3]) x 10 +3
mag[2]mag[3] 就相当于是两位数 比如12
image.png
此时 mag[3] = 0 mag[2] = 2 mag[0] = 1
然后还需要加 3
mag[3] + 3 = 0+3 = 3 也没有进位
那么最终结果为
mag[0] = 1 mag[2] = 2 mag[3] = 3
以上就是一个简单的从字符串123 转换为10进制数，并且保存到数据的过程
String的构造就是类似这样的一个过程
源码
有了以上的介绍之后,我们现在可以贴上该方法的源代码仔细看看.
public BigInteger(String val, int radix) {
//定义了两个变量一个光标，光标记录着应该要处理的数据索引下标
//另一个numDigits 用来保存需要处理的数字位数 也就是有效长度，比如去掉前导零后的
int cursor = 0，numDigits;
final int len = val.length();//传递进来的字符数组的长度
//如果给定的基数，不在合法范围内，那么抛出异常，不会默认处理
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
throw new NumberFormatException("Radix out of range");
//如果字符串长度为0 也是一种非法的参数
if (len == 0)
throw new NumberFormatException("Zero length BigInteger");
// Check for at most one leading sign
int sign = 1;
int index1 = val.lastIndexOf('-');
int index2 = val.lastIndexOf('+');
//符号- + 只能出现一个，而且还必须是第一个位置，否则都不合法
//根据最后一个的索引与0 进行比较，可以简便的判断符号位是否合法
if (index1 >= 0) {
if (index1 != 0 || index2 >= 0) {
throw new NumberFormatException("Illegal embedded sign character");
}
sign = -1;
cursor = 1;
} else if (index2 >= 0) {
if (index2 != 0) {
throw new NumberFormatException("Illegal embedded sign character");
}
cursor = 1;
}
//经过前面的判断，如果有符号位的话，光标的值更新为1 也就是后续不处理符号位
//如果此时光标的值等于字符长度，说明没有有效数字了，将会抛出异常
if (cursor == len)
throw new NumberFormatException("Zero length BigInteger");
// Skip leading zeros and compute number of digits in magnitude
//如果有前导0 ，将会去掉这些，光标的位置也会跟着一起移动
while (cursor < len &&
Character.digit(val.charAt(cursor)， radix) == 0) {
cursor++;
}
//跳过了所有的0之后就不再有有效数据了，说明他就是个0
//哪怕他原来设置的负数的0 将会变为0 的标记
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
}
//记录实际需要处理的数据长度以及对符号位使用signum进行记录
numDigits = len - cursor;
signum = sign;
// Pre-allocate array of expected size. May be too large but can
// never be too small. Typically exact.
//根据前面的公式计算实际需要的二进制位数 numDigits需要处理的数字的长度
//bitsPerDigit 里面记录了每个进制1位数需要的二进制位数，但是放大了1024倍，所以还要除以1024 也就是右移10
//真正的值可能是小数个，除以1024之后变成了取整了，然后再加上一，百分百够用，需要的比特位数保存到numBits
long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
if (numBits + 31 >= (1L << 32)) {
reportOverflow();
}
//numWords 记录的是实际需要的int类型数据的个数，也就是数组的长度
//右移5位就是除以32 就是计算数组的长度，除法会取整，防止1个不足32位的时候，就会变成0了所以numBits加上31 之后再除以32
int numWords = (int) (numBits + 31) >>> 5;
//此时创建真正的保存数据的int数组了
int[] magnitude = new int[numWords];
// Process first (potentially short) digit group
//numDigits 需要处理的数字的个数
//digitsPerInt 保存的是每一个int能够保存的指定数制下的字符长度
//如果有余数，说明有一个不足最大长度的位数
//如果没有余数，那么每一组都是刚好能够保存的最大长度
int firstGroupLen = numDigits % digitsPerInt[radix];
if (firstGroupLen == 0)
firstGroupLen = digitsPerInt[radix];
//第一组数据存放到数组的最后一个
String group = val.substring(cursor， cursor += firstGroupLen);
magnitude[numWords - 1] = Integer.parseInt(group， radix);
if (magnitude[numWords - 1] < 0)
throw new NumberFormatException("Illegal digit");
// Process remaining digit groups
int superRadix = intRadix[radix];
int groupVal = 0;
while (cursor < len) {
group = val.substring(cursor， cursor += digitsPerInt[radix]);
groupVal = Integer.parseInt(group， radix);
if (groupVal < 0)
throw new NumberFormatException("Illegal digit");
// 这个方法是用来累计计算的，方法内部写的很复杂
//其实逻辑很简单，比如一个数字序列1234，求他表示的值是多少
// ( ( (1*10)+2 )*10+3 )*10 +4 = 1234
//这个方法就是用来计算的，只不过每一个位置是一个int 低32位当做数值 高32位当做进位
destructiveMulAdd(magnitude， superRadix， groupVal);
}
// Required for cases where the array was overallocated.
mag = trustedStripLeadingZeroInts(magnitude);
if (mag.length >= MAX_MAG_LENGTH) {
checkRange();
}
}
构造方法运行步骤
简单概括下这个方法:
前面的校验比较简单
- 校验字符的合法性，并且获得符号位
- 经过校验获取出来最终需要处理的字符的长度
然后就开始了计算
在正式计算之前，需要处理最高位，按照前面介绍的，能够表示的指定基数的最多位数进行划分
比如10进制表示9位，那么就是9个字符一组
先判断是否刚好整数倍?
如果不是，比如10位，那么这个最高位这一个数字自己一组，剩下的9位一组，将会被放到两个int中
获得了最高位之后，就开始正式进行计算
如果还有字符需要处理的话 - 按照位数进行截取，比如10进制截取9位
- 截取后转换为数值，然后destructiveMulAdd 这个方法就是第一个参数的数，乘以第二个参数，然后加上第三个参数
就是这样一个过程
( ( (110)+2 )10+3 )*10 +4 = 1234
每一次的循环中int数组的值都会发生变化
最终获得最后的结果
字符串构造方法计算示例
-12345678986543215678901
字符串总长度24
负号占1位， 光标移动一个位置 cursor=1
还有23个字符长度需要处理
需要处理的数字个数为
numDigits = len - cursor = 23
需要的二进制位数为
((numDigits * bitsPerDigit[radix]) >>> 10) + 1
(23*3402)/1024 +1 = 76+1 = 77
需要的int个数， 也就是数组长度为3
(int) (numBits + 31) >>> 5 (77+31)/32 = 3(3.375)
十进制可以保存9位数字
23 不是9的倍数，商2 余数5
所以最高5位将会被截取单独存放
取前面5个数字，也就是12345
12345按照10进制解析为数字，存放到最后一个元素
也就是mag[2] = 12345 光标也跟随移动
数据显然没有处理结束， 进入循环处理， 直到最后结束
第一趟:
先获得接下来的9个字符 也就是 "678986543" ，然后解析为10进制数 678986543
此时
mag[0] = 0，mag[1] = 0 mag[2] = 12345
进入方法 destructiveMulAdd destructiveMulAdd(int数组， 基数， 截取到的值)
他会乘以基数然后加上截取到的数字
image.png
高32位进位，低32位作为得数
此时mag[0] 和mag[1] 不用在乘了，因为此时都是0 ， mag[1] 加上进位即可
此时
mag[0]=0 mag[1] =2874 mag[2] 1263991296
还需要加上678986543
image.png
没有进位
所以第一趟结束之后，最终结果为
mag[0]=0 mag[1] =2874 1942977839
第二趟:
获得接下来的9个字符 也就是 "215678901" ，然后解析为10进制数 215678901
image.png
低32位 为得数 高32位为计数
也就是
得数 -603122176 这是个有符号数
可以使用System.out.println(Integer.valueOf(0xDC0D1600)); 打印出来
进位 452384780
如同我们平时计算乘法一样，还需要计算前一位
此时 mag[0]=0 mag[1] =2874 mag[2] = -603122176
2874 x 10的9次方 = 2874000000000
加上 上一个进位 452384780
结果为 2874452384780
10 1001 1101 0100 0010 1011 0110 1001 1100 0000 1100
所以此时第二位得数为 1119263756(后32位)
进位 10 1001 1101 (高32位) 669
所以此时mag数组为:
mag[0] = 669 mag[1] = 1119263756 mag[2]= -603122176
还需要加上最后截取的数值
image.png
所以最终的结果为
mag[0]=669 mag[1] =1119263756 mag[2] = -387443275
看起来很繁琐复杂，好奇害死猫，分析这么多只是为了更好地了解这一过程
如果没兴趣只需要记住BigInteger可以直接把字符串转换为数值进行存储就好了
转换回来
现在有最后一个问题,如何mag数组转换为原来的数串呢?JDK里面是通过不断做除法取余实现的,BigInteger类的实例在调用toString方法的时候会返回原先的数串.代码如下:
public String toString(int radix) {
if (signum == 0)
return "0";
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;
// Compute upper bound on number of digit groups and allocate space
int maxNumDigitGroups = (4*mag.length + 6)/7;
String digitGroup[] = new String[maxNumDigitGroups];
// Translate number to string, a digit group at a time
BigInteger tmp = this.abs();
int numGroups = 0;
while (tmp.signum != 0) {
BigInteger d = longRadix[radix];
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(tmp.mag),
b = new MutableBigInteger(d.mag);
MutableBigInteger r = a.divide(b, q);
BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
tmp = q2;
}
// Put sign (if any) and first digit group into result buffer
StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
if (signum<0)
buf.append('-');
buf.append(digitGroup[numGroups-1]);// Append remaining digit groups padded with leading zerosfor(int i=numGroups-2; i>=0; i--){// Prepend (any) leading zeros for this digit groupint numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();if(numLeadingZeros !=0)
buf.append(zeros[numLeadingZeros]);
buf.append(digitGroup[i]);}return buf.toString();}privatestaticString zeros[]=newString[64];static{
zeros[63]="000000000000000000000000000000000000000000000000000000000000000";for(int i=0; i<63; i++)
zeros[i]= zeros[63].substring(0, i);
}
问题回答
方法 destructiveMulAdd destructiveMulAdd(int数组， 基数， 截取到的值), 会乘以基数然后加上截取到的数字
如果此时前面的数字+ 窃取到的数字 大于integeter 最大数， 必须有个变量来存储，此时long 就是唯一选择。 如果有BigLong， 在此种情况下，就没有基本类型可以处理了。
// Multiply x array times word y in place, and add word z
private static void destructiveMulAdd(int[] x, int y, int z) {
// Perform the multiplication word by word
long ylong = y & LONG_MASK;
long zlong = z & LONG_MASK;
int len = x.length;
long product = 0;
long carry = 0;
for (int i = len-1; i >= 0; i--) {
product = ylong * (x[i] & LONG_MASK) + carry;
x[i] = (int)product;
carry = product >>> 32;
}
// Perform the addition
long sum = (x[len-1] & LONG_MASK) + zlong;
x[len-1] = (int)sum;
carry = sum >>> 32;
for (int i = len-2; i >= 0; i--) {
sum = (x[i] & LONG_MASK) + carry;
x[i] = (int)sum;
carry = sum >>> 32;
}
}
网友评论