BigInteger

2022-04-08 本文已影响0人程序员札记

昨天在讲算法的时候，突然提到超大数。今天就讲一下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值大小范围是-2^31至231-1)，若是3进制3^{19<2147483647<3}20,因此每次就可以选择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进制数可以表示?

x位二进制能够表示的最大值为

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;
        }
    }

BigInteger

什么是BigInteger（定义）

属性

构造函数

算法基础

位数表示

构造整数

源码

字符串构造方法计算示例

转换回来

问题回答

猜你喜欢

热点阅读