Java大数源码剖析(一) - BigInteger的底层数据结构

发表于 更新于 阅读次数：

Java大数源码剖析(一) - BigInteger的底层数据结构

本系列文章对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的成员变量/常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;