本系列文章对Java大数类源码进行剖析, Java大数类包括java.math.BigInteger和java.math.BigDecimal, 本人使用的JDK版本为13.0.2
本系列文章按照以下顺序 :
- BigInteger的介绍和底层数据结构 (一篇文章)
- 依次剖析BigInteger各个常用方法的源码实现(从简到难) (若干篇文章)
- 讲解BigDecimal的的介绍和底层数据结构 (一篇文章)
- 依次剖析BigInteger各个常用方法的源码实现(从简到难) (若干篇文章)
- 后续(文章)计划 : 利用C++实现自己的BigNumber库, 这是我剖析java大数类的最终目的,最终会形成一套处理大整数的C++开源库PGBigNumber
BigInteger介绍
BigInteger是Java标准库提供的大整数类,提供对整数的各种操作和常用算法。与普通的int和Integer相比,BigInteger可以对大整数进行操作,而Java内置的整形最长的整形是long(64位有符号整数),一旦对需要多于64位的整数(说63位也许更好,因为有一位是符号位)进行处理时就需要BigInteger。
注意BigInteger是不可变的,也就是说,一旦创建就不能改变其数值。同时也决定了BigInteger提供的运算方法都是非本地算法。
注 : BigInteger所在包为java.math
BigInteger的主要操作
BigInteger以成员方法的形式提供和内置整型类似的操作, 除此之外还提供abs求绝对值、max/min求最大最小值、gcd求最大公约数······
本系列文章对以下方法的源码进行剖析:
- add/subtract (二)
- multiply/divide (三)
- 位运算 (四)
- 常用的构造方法 (五)
- max/min/abs/negate/ (六)
- mod/reminder/divideAndReminder (七)
- power/sqrt/gcd (八)
BigInteger的底层数据结构
前文说过, 我剖析Java的大数库的最终目的是开发自己的基于C++的PGBigNumber库, 那么为什么我不研究现在已有的C++的大数库的源码呢?
这是因为, 我在github上找到的基于C++的大数库都是底层一个string, 每一个char就代表十进制的一个bit, 这显然是简单的, 但是同时也是低效的, CPU或者操作系统平台提供的对于32/64位整数的操作被利用的太少, 每次都操作十进制的一个bit, 对应于二进制的4个bit, 而利用内置的操作符依次就能至少能操作32个二进制位, 这是时间上的利用十进制存放大整数的劣势。
空间上,C++中每个char是一个byte,也就是说本来能存放8个二进制位的char仅仅被使用了4个bit,空间显然占用很多。并且,由于十进制的存储,二进制位操作显得十分不方便。
所以,我想到了利用二进制存放大整数,但是搜来搜去也没有找到有C++开源库采用这种方法,于是我去Java的源码中找了一下BigInteger的实现。很好!Java的BigInteger的底层正是利用二进制存放大整数。
**简单来说,**BigInteger的底层是利用一个int的数组(称为mag)存储大整数,也就是说,当要存放的整数大于32位时,就会被分割成32位为一组的形式,每一组就作为底层数组的一个元素。并且,BigInteger的底层数组mag时大端存放的,也就是说mag[0]、mag[1]…mag[mag.length - 1]分别代表整数的最高32位、次高32位…最低32位。
**并且,**BigInteger的mag数组仅仅用来存放绝对值的二进制位,其符号被signum存放,signum为0即代表0;signum为1即代表正数、signum为-1即代表负数。
为什么不直接按照补码存放呢? 我认为,是为了使操作的算法更为高效和方便。
-
如果采用补码,* /等操作将会变得很复杂,并且,获取相反数、绝对值等算法的复杂度也会由常数变为线性。
-
由于底层数组是final的,仅仅想改改符号位也是不可能的,必须要深拷贝一份, 如果有了signum存放符号, 求个相反数只需要求反个signum, 拷贝mag只需浅拷贝。
-
有了signum使判断是否为0十分方便。
BigInteger的成员变量/常量
final int signum; // 符号标志, -1 : 负数, 0 : 零, 1 : 正数
final int[] mag; // 存放大整数二进制位的数组, 大端存储
/*
** 下面的变量都是为了懒求值而设置的, 暂时不用管.
* 所谓懒求值是指当用到的时候才求值;
*
** 而求过之后由于BigInteger是不可变的,
* 这些所求也不会变, 所以就利用变量存下,
* 当第二次求这些的时候, 直接返回即可;
*
** 之所以存放这些值+1或+2(plusOne plusTwo),
* 是为了方便判断是否被求过.
*/
private int bitCountPlusOne;
private int bitLengthPlusOne;
private int lowestSetBitPlusTwo;
private int firstNonzeroIntNumPlusTwo;
下一篇文章 : Java大数源码剖析(二) - BigInteger的加减操作