欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[十六]基础类型BigInteger简介

程序员文章站 2022-04-14 20:33:05
本文对BigInteger进行了简单介绍,包括BigInteger属性结构,存储形式,原码补码反码的计算方式,BigInteger的String构造方法源码解析,以及计算过程示例,另外分类简单介绍了方法API ......
 
 
biginteger和bigdecimal都是java针对大数提供的类
超出了java的表示范围
 

属性简介

借助于signummag 来实现数据的符号位和实际数据的保存
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表示范围是:   
-231 ~ 231-1     也就是   -2147483648 ~ 2147483647
对于十进制
可以表示10位十进制数字
但是 2147483648 (2147483647+1)  仍旧是10位数字却溢出了
所以选择保存9位十进制数
 
所以每个int   十进制下最大值为10的9次方
对于二进制
最大值 231-1 ,所以只能保存30位 2进制数
 
所以每个int   二进制下最大值为2的30次方
对于三进制
319 =1162261467 <2147483647<320 = 3486784401  
所以能够保存19位 三进制数
 
所以每个int   三进制下最大值为3的19次方
对于四进制
415 = 1073741824 < 2147483647 < 416 = 4294967296  
所以能够保存15位 四进制数
 
所以每个int  四进制下最大值为4的15次方
对于十六进制
167 =268435456 < < 2147483647 < 168 =  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 0x3b9aca001   + mag[1] x 0x3b9aca00
0  
就如同十进制的数12的计算方式为1x101 + 2 x100 =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位
(0)
打赏 [十六]基础类型BigInteger简介 微信扫一扫

相关文章:

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论

[十六]基础类型BigInteger简介
验证码: [十六]基础类型BigInteger简介
Copyright © 2017-2022  保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com