[十六]基础类型BigInteger简介

程序员文章站 2022-07-02 14:21:11

本文对BigInteger进行了简单介绍，包括BigInteger属性结构,存储形式,原码补码反码的计算方式,BigInteger的String构造方法源码解析,以及计算过程示例,另外分类简单介绍了方法API ......

biginteger和bigdecimal都是java针对大数提供的类

超出了java的表示范围

属性简介

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

final int signum 保存biginteger的符号

负数	-1
0	0
正数	1

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

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

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

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

对于biginteger 他的数据打开就是这么一种形式

[ 101....32位....1] [ 110....32个....1] ....n个..... [ 0110....32个....1]

它的真值的计算方法与其他的二进制序列一样的

二进制为 0111 1110 的十进制为126 相信谁都会计算，biginteger也是如此的

尤其是对于biginteger字符串参数的构造形式

千万不要以为就是把字符的编码或者字符转换成数字切段存放到int数组中

他存放的都是转换后的真值

下面会详细介绍

使用字节数组构造

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

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

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

不过要注意的是，

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

正数的补码与原码相同

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

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

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

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

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

原码/反码/补码

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

原码	符号位+数值位符号位为0 表示正数，符号位为1 表示负数数值位就是真值的绝对值又被称为带符号的绝对值表示
反码	正数的反码为其原码负数的反码为其原码的除符号位外，逐位取反
补码	正数的补码为其原码负数的补码为其反码+1

补码计算步骤

第一步求原码: 先写出来她的原码--->符号位+数值位(绝对值)

第二步求反码:

如果是正数反码与原码一样

如果是负数反码为原码取反(除符号位外，逐位翻转)

第三步求补码:
如果是正数补码与原码一样
如果是负数补码为反码 + 1

第四步扩充:
如果不足数据类型的宽度，将需要填充到指定宽度
符号位扩充，也就是正数补0 负数补1

总结
不管什么形式，第一位始终都是符号位，0 表示正数， 1表示负数
正数原码/反码/补码全都一样，知道一种就直接得到另外的形式
负数如果知道补码，想要得到他的原码，只需要对补码再一次的求补码即可

示例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表示范围是:

-2³¹ ~ 2³¹-1 也就是 -2147483648 ~ 2147483647

对于十进制

可以表示10位十进制数字

但是 2147483648 (2147483647+1) 仍旧是10位数字却溢出了

所以选择保存9位十进制数

所以每个int 十进制下最大值为10的9次方

对于二进制

最大值 2³¹-1 ，所以只能保存30位 2进制数

所以每个int 二进制下最大值为2的30次方

对于三进制

3¹⁹ =1162261467 <2147483647<3²⁰ = 3486784401

所以能够保存19位三进制数

所以每个int 三进制下最大值为3的19次方

对于四进制

4¹⁵ = 1073741824 < 2147483647 < 4¹⁶ = 4294967296

所以能够保存15位四进制数

所以每个int 四进制下最大值为4的15次方

对于十六进制
16⁷ =268435456 < < 2147483647 < 16⁸ = 4294967296
所以能够保存7位十六进制数

所以每个int 十六进制下最大值为16的7次方

所以就有了这么两个映射数组
digitsperint
表示每个int 可以表示的，指定进制下数字的位数，下标索引就是进制基数
比如可以表示十六进制的位数为digitsperint[16] = 7
intradix
表示每个int可以表示的指定进制下的最大值，下标索引就是进制基数
比如每一位int 可以表示的十进制的最大值为 intradix[10] = 0x3b9aca00=1，000，000，000

其实intradix这个数就是:
biginteger在这个基数下的基数
这句话有点绕，biginteger内部是数组，假如为mag[0] mag[1] intradix[10] = 0x3b9aca00
那么也就是，biginteger在十进制，也就是10为基数下的基数为0x3b9aca00
那么这个值就是 mag[0] x 0x3b9aca00¹ + mag[1] x 0x3b9aca00⁰就如同十进制的数12的计算方式为1x10¹ + 2 x10⁰ =12 一样的道理
下面还会继续说明

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

biginteger内部使用int数组表示
普通数值使用每个数值位上的数字进行表示

一个biginteger有多个int
一个普通数值有多个数字位

每个int能够表示的指定进制的最大值--intradix 中保存的数据

其实就是 biginteger 的基于每个int作为一个元素的进制基数

假设r为指定的基数
l为指定基数的数字的长度

那么用多少位2进制数可以表示?

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

l位r进制的数能够表示的最大值为

比如r=10 l=2 也就是十进制两位数能够表示的最大值为: 10的平方减1 等于 99

解上面的方程，可以得出来
x的长度为：l 乘以以2为底r的对数

内部还有一个数组

这个数组的值就是以2为底r的对数的值，然后乘以1024，然后进行向上取整

bitsperdigit 就是每个数字需要的比特位数乘以1024后在取整
之所以乘以1024然后在取整
应该是为了简化运算，这个数必然要是2的n次方，计算机移位最快
当然，这个地方乘以1024 实际使用的时候必然也还得除以1024

以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" ，转换为数字1，然后保存到mag[3] = 1 (我们此处假定从数组最后开始存放)

2. 找到第二个字符 "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" ，转换为数字3，然后计算 (mag[2]mag[3]) x 10 +3
mag[2]mag[3] 就相当于是两位数比如12

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

}

构造方法运行步骤

简单概括下这个方法:

前面的校验比较简单

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

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

然后就开始了计算

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

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

先判断是否刚好整数倍?

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

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

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

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

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

就是这样一个过程

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

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

最终获得最后的结果

字符串构造方法计算示例

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

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

-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数组，基数，截取到的值)
他会乘以基数然后加上截取到的数字

高32位进位，低32位作为得数
此时mag[0] 和mag[1] 不用在乘了，因为此时都是0 ， mag[1] 加上进位即可
此时
mag[0]=0   mag[1] =2874     mag[2] 1263991296
还需要加上678986543

没有进位
所以第一趟结束之后，最终结果为
mag[0]=0   mag[1] =2874      1942977839

第二趟
获得接下来的9个字符也就是 "215678901" ，然后解析为10进制数 215678901

低32位为得数高32位

打赏

微信扫一扫

javaDay01_小练习

package zrs; public class Demo4 { public static void main(String[] args) {... [阅读全文]
javaDay01_2

package zrs; public class Demo3 { public static void main(String[] args) {... [阅读全文]
PHP简单的长文章分页教程附源码

PHP简单的长文章分页教程附源码。本文将content.txt里的内容分割成3页，这样浏览起来用户体验很好。 ... [阅读全文]
webservice之实现天气预报

前通过传智的视频自学了webservice的基本使用，也了解到webservice就是一种跨编程语言和跨操作系统平台的远程调用技术。对于这些理论知... [阅读全文]
一份针对于新手的多线程实践--进阶篇

前言在上文 "《一份针对于新手的多线程实践》" 留下了一个问题：这只是多线程其中的一个用法，相信看到这里的朋友应该多它的理解更进一步了。再给大... [阅读全文]