Java_BigInteger(11)

BigInteger

对于长度超过了 Long 的大整数就需要 BigInteger 来进行处理了,底层是 int[] 数组

内部封装了许多常用的数学运算方法,BigInteger 定义在 java.math 包下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Test {
  public static void main(String[] args) {
    //long l = 12345678901234567890L; //out of range
    String s = "12345678901234567890";
    BigInteger bi1 = new BigInteger(s);
    BigInteger bi2 = new BigInteger(s);
    System.out.println(bi1.add(bi2)); //24691357802469135780
    System.out.println(bi1.subtract(bi2)); //0
    //152415787532388367501905199875019052100
    System.out.println(bi1.multiply(bi2)); 
    System.out.println(bi1.divide(bi2)); //1
    //商和余数
    BigInteger[] arr = bi1.add(bi2).divideAndRemainder(bi2);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " "); // 2, 0
    }
  }
}

查看 BigInteger 类的定义

1
public class BigInteger extends Number implements Comparable<BigInteger> {}

因为继承了 Number 类所以可以通过 xxxValue 方法转换为基本类型,如果超出范围了,则转换后会丢弃高位的数据,对于精准地转换为整数的基本类型,提供了 xxxValueExact 方法,对于超出范围的情况会抛出异常 ArithmeticException

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Test {
  public static void main(String[] args) {
    String s1 = "9223372036854775808";
    BigInteger bi1 = new BigInteger(s1);
    System.out.println(bi1.longValue()); //-9223372036854775808
    System.out.println(bi1.doubleValue()); //9.223372036854776E18
    //System.out.println(bi1.longValueExact()); 
    //ArithmeticException: BigInteger out of long range
    String s2 = "9223372036854775807";
    BigInteger bi2 = new BigInteger(s2);
    System.out.println(bi2.longValueExact()); //9223372036854775807
  }
}

关键的类成员

至于 BigInteger 重要的类成员有下面两个

1
2
final int signum;
final int[] mag;

signum 用来区分正和负的符号,1 表示正,-1 表示负,0 则表示数值为 0

mag 则是 magnitude 的缩写,这个数组就是用来保存大整数数值的,如果保存的数值是 0,则 mag 数组就是一个空数组,长度为 0,对于非 0 的数值则采用的是 big-endian 大端的保存顺序,即数值的高位存入低地址,低位存入高地址

查看入参为 String 的构造方法,方法抬头上的注释说了字符串不能有任何无关的字符,例如空格

1
2
3
4
5
public BigInteger(String val) {
  this(val, 10); //默认10进制
}
//可以指定String中数值的进制
public BigInteger(String val, int radix) {}

在查看构造方法具体实现之前还要先理解 digitsPerInt、intRadix 、bitsPerDigit 这三个类成员

int 十进制数的范围是 -2147483648 到 2147483647,所以可以按 9 位进行划分,例如一个大整数 111111111222222222333333333 可以划分为 111111111、222222222、333333333 三段

但是要支持不同进制的数,不同进制的数划分的位数又不同,例如二进制可以按 30 位来划分,三进制可以按 19 位来划分 ($3^{19}<2147483647<3^{20}$),十六进制可以按 7 位来划分,最大的进制可以到 36 进制,所以 digitsPerInt 就是用来记录不同进制的划分位数的,数组索引对应进制

1
private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11, 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};

intRadix 保存了每个进制按照 digitsPerInt 中的位数划分后 10000… 的值,数组索引对应进制,例如十进制是按 9 位划分,则 intRadix 中对应十进制的就是 0x3b9aca00 即 1000000000 即 intRadix 可以看成是 mag 的基数,例如十进制数 123 可以拆分为 $1 * 10^2+2 * 10^1+3 * 10^0$ 基数为 10,而十进制 mag 的基数为 intRadix[10],也可以拆分 $$mag[0]mag[1]mag[2]=mag[0]*intRadix[10]^0+mag[1]*intRadix[10]^1+mag[2]*intRadix[10]^2$$

1
private static int intRadix[] = {0, 0, 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800, 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61, 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000, 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d, 0x6c20a40,  0x8d2d931,  0xb640000,  0xe8d4a51,  0x1269ae40, 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41, 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400};

而 bitsPerDigit 则是用于计算这个大数总共需要多少位,也即可以计算出 mag 初始化时的大小

1
private static long bitsPerDigit[] = {0, 0, 1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672, 3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633, 4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210, 5253, 5295};

将一个 radix 进制有 m 位数的大数,转换为对应的二进制数需要的 bit 位 $radix^m=2^x$ 即 $x=m*log_2(radix)$ ,但 $log_2(radix)$ 通常是个小数,所以 BigInteger 的作者将其扩大了 1024 倍后再取了整,例如 $log_2(3)*1024$ 约等于1623.0016… ,作者取的是 1624

构造方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public BigInteger(String val, int radix) {
  int cursor = 0, numDigits;
  final int len = val.length();
  //检擦进制是否正确,len是否为0,源码省略...
  //检查是否有+、-的前导符号,源码省略...
  
  //忽略前导的0
  while (cursor < len &&
         Character.digit(val.charAt(cursor), radix) == 0) {
    cursor++;
  }
	//若字符串全是0,则将signum置0,mag数组置空
  if (cursor == len) {
    signum = 0;
    mag = ZERO.mag;
    return;
  }
  numDigits = len - cursor; //实际的有效数字
  signum = sign; //sign是在前面检查前导符号+、-时定义的
  
  //计算将这个大数转换为二进制数需要多少位,因为在bitsPerDigit中扩大了1024倍
  //这里就右移10位相当于除以1024,整除丢失小数,所以+1保证不会比真实值小
  long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
  if (numBits + 31 >= (1L << 32)) { //4294967296
    reportOverflow(); //说明BigInteger也是有限大小的
  }
  //右移5相当于除以32,因为int只有32位,得到mag应该初始化的大小
  //+31是防止不够32除了之后变成0了
  int numWords = (int) (numBits + 31) >>> 5;
  int[] magnitude = new int[numWords];

  //开始按照digitsPerInt中的范围截取字符串中的数了
  //划分后大概率会有一段长度是小于划分长度的,先处理这段小的
  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");
  
  //继续处理剩下的
  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
    destructiveMulAdd(magnitude, superRadix, groupVal);
  }
  mag = trustedStripLeadingZeroInts(magnitude);
  if (mag.length >= MAX_MAG_LENGTH) {
    checkRange();
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
final static long LONG_MASK = 0xffffffffL;
//x为magnitude数组,第一次传入的时候数组末尾已经填充了一段值了
//y为数组的基数,十进制就是intRadix[10]的值1000000000
//z为大数划分后的一段分组对应的数值
private static void destructiveMulAdd(int[] x, int y, int z) {
  long ylong = y & LONG_MASK;
  long zlong = z & LONG_MASK;
  int len = x.length;
  long product = 0;
  long carry = 0;
  
  //从低位到高位分别与y相乘,并加上上一次计算的进位  
  for (int i = len-1; i >= 0; i--) {
    product = ylong * (x[i] & LONG_MASK) + carry;
    //取乘积的低32位
    x[i] = (int)product;
    //高32位为进位数,留到下次循环相加  
    carry = product >>> 32;
  }
  
  //执行加z的操作
  long sum = (x[len-1] & LONG_MASK) + zlong;
  //mag数组末尾保留相加结果的低32位
  x[len-1] = (int)sum;
  //高32位为进位数  
  carry = sum >>> 32;
  //将进位向高位加上去
  for (int i = len-2; i >= 0; i--) {
    sum = (x[i] & LONG_MASK) + carry;
    //取低32位
    x[i] = (int)sum;
    //高32位做进位
    carry = sum >>> 32;
  }
}

在构造方法中看到有 reportOverflow() 方法,说明 BigInteger 也是有大小限制的

类中还定义了 checkRange 方法,即 BigInteger 的 mag 数组长度不能超过 67108864

1
2
3
4
5
6
private static final int MAX_MAG_LENGTH = Integer.MAX_VALUE / Integer.SIZE + 1; // (1 << 26)
private void checkRange() {
  if (mag.length > MAX_MAG_LENGTH || mag.length == MAX_MAG_LENGTH && mag[0] < 0) {
    reportOverflow();
  }
}

构建过程实例

1
BigInteger bi = new BigInteger("-12345678986543215678901");

字符串长度 24,首先除去前导的 - 号,cursor 加 1,signum置 -1

需要处理的数字有效位数 numDigits = len - cursor = 23

对应需要的二进制位数 ((numDigits * bitsPerDigit[radix]) »> 10) + 1

$(23*3402)/1024+1=76+1=77$

需要划分的段数, 即 mag 数组长度 (int) (numBits + 31) »> 5, $(77+31)/32 = 3(3.375)$

numDigits % digitsPerInt[radix],$23%9=5$

取前面 5 个字符 “12345” 按照十进制解析为数字放到 mag 的末尾,即 mag[2] = 12345


进入循环

第一轮,取接下来 9 个字符 “678986543” 并解析为十进制数 678986543

此时 mag 数组 [0] = 0、mag[1] = 0、mag[2] = 12345

进入 destructiveMulAdd(mag[], 基数, 截取到的值) 方法

y = 1000000000、z = 678986543

product = ylong * (x[i] & LONG_MASK) + carry; 即 product = 1000000000 * 12345 + 0

对应二进制为‭ 1011 0011 1010 0100 1011 0101 0110 1111 1010 0000 0000‬

x[i] = (int) product; 取低 32 位,即 x[2] 对应的十进制为 ‭1263991296‬

carry = product »> 32; 即 carry = 1011 0011 1010,对应十进制为 2874

接下来 mag[0] 和 mag[1] 此时都为 0,只用 mag[1] 加上进位即可

所以 mag[0] = 0、mag[1] = 2874、mag[2] = 1263991296

然后是加 z 的操作,结果为 mag[0] = 0、mag[1] = 2874、mag[2] = 1942977839


第二轮,取接下来 9 个字符 “215678901” 并解析为十进制数 215678901,即 z 的值

1942977839 乘以基数 + 此时为 0 的进位

高 32 位 ‭0001 1010 1111 0110 1101 1000 0000 1100 做进位,即进位对应的十进制为 452384780

低 32 位 1101 1100 0000 1101 0001 0110 0000 0000‬ 为得数,即 x[2] 对应的十进制为 -603122176

此时 mag[0] = 0、mag[1] = 2874、mag[2] = -603122176

2874 * 基数 + 进位 = 2874452384780

高 32 位 10 1001 1101 做进位,即 669

低 32 位 0100 0010 1011 0110 1001 1100 0000 1100 做得数,即 1119263756

此时 mag[0] = 669、mag[1] = 1119263756、mag[2]= -603122176

然后是加 z 操作,结果为 mag[0] = 669、mag[1] = 1119263756、mag[2] = -387443275


所以大整数 12345678986543215678901 被分为 669、1119263756、-387443275 三段保存

[0] [0] [12345]

[0] [2874] [1942977839]、 $12345*10^9+678986543$

[669] [1119263756] [-387443275]、$(12345*10^9+678986543)*10^9+215678901$

$215678901*{10^9}^0+678986543*{10^9}^1+12345*{10^9}^2$

所以也可以说是被转化为 $10^9$ 进制的数保存在 mag 数组中,只是由于 mag 数组的元素是 int 只有 32 位,有高 32 位进位的操作

$mag[0]mag[1]mag[2]=mag[0]*intRadix[10]^0+mag[1]*intRadix[10]^1+mag[2]*intRadix[10]^2$

运算方法

以后再说吧 ……

不过 divide 方法使用的 MutableBigInteger 类好像有点东西


以上内容是玉山整理的笔记,如有错误还请指出