[十六]基础类型BigInteger简介

BigInteger和BigDecimal都是Java针对大数提供的类

超出了java的表示范围

属性简介

借助于signum和mag 来实现数据的符号位和实际数据的保存

final int signum 保存BigInteger的符号

final int[] mag;保存数字的数据 字节序为大端模式，大端模式就是低地址存储高位

数组的第一个元素必须是非0的，也就是如果有前导零将会被移除

这样可以保证每个数都有一个唯一的表示形式

这种要求下 BigInteger的0有一个0长度的数组保存

使用字节数组构造

内部是Int数组，一个int 32位就是 4个字节，所以自然是可以使用字节对BigInteger进行构造的

提供了两种形式的字节构造方法，可以指定符号的

使用字节进行构造，就是把所有的字节填充到int数组中

不过要注意的是，

计算机中存储的数值都是补码的形式

正数的补码与原码相同

负数的补码是他的原码取反再加一

就是把这些字节的补码按照顺序拼在一起，组合成int数组

• 如果是一个负数，会先得到真值的绝对值
• 如果有前导零，还会去掉所有的前导零

而且，是大端排序，大端排序，大端排序的把最终的数据存储起来

也就是说int数组中保存的都是真值的绝对值，使用专门的符号位记录正负和0

原码/反码/补码

先回顾下原码/反码/补码 的概念

补码计算步骤

示例1

示例2

通过这两个例子应该可以看得出来，数值都是补码形式存放

字节存储的也是补码 ， int存储的也是补码，

所以使用字节构造 就是把所有的补码拼凑在一起就好了

拼凑排列好的补码，如果是正数，那么原码/反码/补码全都一样，存储的就是这个值

如果是负数，还需要取他的绝对值，绝对值就是 再求一次补码，去掉符号位就是绝对值了

BigInteger数组中，存储的都是真值的绝对值的补码，真值绝对值得补码，其实就是原码去掉符号位嘛，一个意思

就像上面的第二个例子  得到的补码为:  

1000  0011  1111 0111  0000  0000  0101 1001

实际存储的是:

0111  1100   0000 1000  1111  1111 1010  0111

使用String构造

String作为参数的构造方法有两种形式

本质上只是一种，那就是指定基数的字符串转换为BigInteger

简化形式就是默认十进制的形式

通过String构造BigInteger的逻辑比较简单，但是实现看起来会有些令人模糊

接下来我们先介绍一点相关的计算基础

算法基础

int能够支撑的数据长度以及基数

我们知道，存储实际数据的是int数组

int表示范围是:   

-231 ~ 231-1     也就是   -2147483648 ~ 2147483647

同理它内部也有两个针对Long 的数组，用于内部计算使用

说到这，我们再回头看看上面介绍的几个数组

以上是String构造BigInteger的用到的一些基本概念

构造方法源码解析

我们从构造方法入手，简单介绍下内部是如何运作的

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();

}

}

构造方法运行步骤

简单概括下这个方法:

前面的校验比较简单

1. 校验字符的合法性，并且获得符号位

2. 经过校验获取出来最终需要处理的字符的长度

然后就开始了计算

在正式计算之前，需要处理最高位，按照前面介绍的，能够表示的指定基数的最多位数进行划分

比如10进制表示9位，那么就是9个字符一组

先判断是否刚好整数倍? 

如果不是，比如10位，那么这个最高位这一个数字自己一组，剩下的9位一组，将会被放到两个int中

获得了最高位之后，就开始正式进行计算

如果还有字符需要处理的话

1. 按照位数进行截取，比如10进制截取9位

2. 截取后转换为数值，然后destructiveMulAdd  这个方法就是第一个参数的数，乘以第二个参数，然后加上第三个参数

就是这样一个过程

( ( (1*10) 2 )*10 3 )*10 4 = 1234

每一次的循环中int数组的值都会发生变化

最终获得最后的结果

字符串构造方法计算示例

使用字符串"-12345678986543215678901"  进行构造

我们按照方法的计算步骤走一下这个过程 

看起来很繁琐复杂，好奇害死猫，分析这么多只是为了更好地了解这一过程

如果没兴趣只需要记住BigInteger可以直接把字符串转换为数值进行存储就好了

其他构造方法

另外还有两个构造方法

public BigInteger(int bitLength， int certainty， Random rnd) 

          构造一个随机生成的正 BigInteger，它可能是一个具有指定 bitLength 的素数

public BigInteger(int numBits， Random rnd)

          构造一个随机生成的 BigInteger，它是在 0 到 (2numBits - 1)（包括）范围内均匀分布的值

方法简介

基础方法

取模与求余对比

1. 求 整数商： c = a/b;
2. 计算模或者余数： r = a - c*b.

求模运算和求余运算在第一步不同:  取余运算在取c的值时，向0 方向舍入; 而取模运算在计算c的值时，向负无穷方向舍入; 因此，求模时结果的符号与b一致，求余时结果的符号与a一致 如果a，b都是正整数的话，求模与求余没有区别 mod(BigInteger)  返回其值为 (this mod m) 的 BigInteger，取模不同于 remainder BigInteger modPow(BigInteger exponent，BigInteger m) BigInteger modInverse(BigInteger m)

bitCount与bitLength

valueOf(long)

equals(Object)

toString hashCode CompareTo

素数相关

特殊的"位操作"

toByteArray

总结

要记住，内部的存储int数组 是final int[] mag;  所以是不可变的

他只是用来表示超出Java范围内的数值

本身的方法虽然内部细节特殊

但是外部呈现并没有什么特别的，只不过不能使用平时的 -*/符号，需要使用专门的方法

它提供了BigInteger大数值作为数值的基本运算的对应方法

并且还提供了java.lang.Math 的所有相关方法

另外，BigInteger 还提供以下运算：模算术、GCD 计算、质数测试、素数生成、位操作以及一些其他操作