Java BigInteger

Java

大数

BigInteger

底层维护两个变量
既然一个int范围有限，那么BigInteger就维护int数组
另外符号单独一个变量维护

BigInteger.java
1
2
3
4
5
public class BigInteger extends Number implements Comparable<BigInteger> {
    final int signum;
    final int[] mag;
    //...
}

无符号整数

BigInteger单独维护符号，因此数组每位都当做无符号数，即相当于最大无符号数作为进制
然而Java里并没有无符号整数，如果数组里某个数字二进制首位是1，那么会被当成一个负数。为了解决这一问题，实现中定义了一个long型掩码

BigInteger.java
1
final static long LONG_MASK = 0xffffffffL;

实现中用int与掩码进行与操作，结果转成long,数值上和无符整数一致

Sample
1
2
3
int a = 0x80000001;  //-2147483647
long b = a;  //-2147483647
long c = a & 0xffffffffL;  //2147483649

合并两个数组

BigInteger.java
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
private static int[] add(int[] x, int[] y) {
    //交换，使得第一个参数长度长
    if (x.length < y.length) {
        int[] tmp = x;
        x = y;
        y = tmp;
    }

    int xIndex = x.length;
    int yIndex = y.length;
    //按照较长的数组大小分配结果数组
    int result[] = new int[xIndex];
    //采用long避免溢出
    long sum = 0;
    if (yIndex == 1) {
        sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
        result[xIndex] = (int)sum;
    } else {
        //从末尾开始相加，都转成正数
        while (yIndex > 0) {
            sum = (x[--xIndex] & LONG_MASK) + (y[--yIndex] & LONG_MASK) + (sum >>> 32);
            //强制截断
            result[xIndex] = (int)sum;
        }
    }
    //如果有进位继续向前传递进位
    boolean carry = (sum >>> 32 != 0);
    while (xIndex > 0 && carry)
        carry = ((result[--xIndex] = x[xIndex] + 1) == 0);

    //如果还剩下位数直接拷贝
    while (xIndex > 0)
        result[--xIndex] = x[xIndex];

    //如果还有进位，说明一开始分配空间不够，需要再填一位
    if (carry) {
        int bigger[] = new int[result.length + 1];
        System.arraycopy(result, 0, bigger, 1, result.length);
        bigger[0] = 0x01;
        return bigger;
    }
    return result;
}

不可变

BigInteger是不可变的，所有操作都会返回新的对象

加减法

加法逻辑比较直观

  • 判断是否其中一个是0，是的话直接返回另一个数
  • 同符号，做加法，符号不变构造结果
  • 不同符号，先比较绝对值，不等的话做减法，确保大减小，清除起始的0并判定符号构造结果
BigInteger.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public BigInteger add(BigInteger val) {
    if (val.signum == 0)
        return this;
    if (signum == 0)
        return val;
    if (val.signum == signum)
        return new BigInteger(add(mag, val.mag), signum);

    int cmp = compareMagnitude(val);
    if (cmp == 0)
        return ZERO;
    int[] resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(val.mag, mag));
    resultMag = trustedStripLeadingZeroInts(resultMag);

    return new BigInteger(resultMag, cmp == signum ? 1 : -1);
}

减法套路和加法完全一致

BigInteger.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public BigInteger subtract(BigInteger val) {
    if (val.signum == 0)
        return this;
    if (signum == 0)
        return val.negate();
    if (val.signum != signum)
        return new BigInteger(add(mag, val.mag), signum);

    int cmp = compareMagnitude(val);
    if (cmp == 0)
        return ZERO;
    int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
                       : subtract(val.mag, mag));
    resultMag = trustedStripLeadingZeroInts(resultMag);
    return new BigInteger(resultMag, cmp == signum ? 1 : -1);
}

数组采用大端存储的方式，mag[0]存高位，因此运算后可能存在数组前几个数字都是0，采用数组拷贝的方式清除掉

BigInteger.java
1
2
3
4
5
6
7
8
9
private static int[] trustedStripLeadingZeroInts(int val[]) {
    int vlen = val.length;
    int keep;

    // Find first nonzero byte
    for (keep = 0; keep < vlen && val[keep] == 0; keep++)
        ;
    return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
}

因为没有了起始的0，因此数组内每个数字都是有效的，比较绝对值时更加直观，比较长度即可初步判断大小

BigInteger.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
final int compareMagnitude(BigInteger val) {
    int[] m1 = mag;
    int len1 = m1.length;
    int[] m2 = val.mag;
    int len2 = m2.length;
    if (len1 < len2)
        return -1;
    if (len1 > len2)
        return 1;
    for (int i = 0; i < len1; i++) {
        int a = m1[i];
        int b = m2[i];
        if (a != b)
            return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
    }
    return 0;
}

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2018/05/11/java-biginteger/