Java大數BigInteger的原理

引言

在java中，整型分為Integer（4 bytes 32位）和Long（8 bytes 64位）兩種類型，是以java中一個整數最多隻能占64個bits，并且java中不存在無符号數，無論是Integer類型還是Long類型都是有符号數。當我們需要表示一個超過64 bits的數時，就需要用到BigInteger類型，BigInteger是java包提供的一個大數類型，它的原理就是将大數拆分成一個int[]表示，理論上該int[]數組的長度可以無限增大（大數規定int[]長度不超過1^26），該類提供了普通整型具有的所有運算方法，包括加減乘除，與或非等。本文介紹大數的構造和基本計算原理。

主要成員變量

final int signum;  //符号位，1表示正數，-1表示負數，0的符号位為0

   
    final int[] mag;  //int數組，從index=0開始表示大數的最高位

     
    private int bitCount; //大數的bit個數加1，預設值為0，當需要時才會被初始化

   
    private int bitLength;

    
    private int lowestSetBit;

    
    private int firstNonzeroIntNum;
           

最重要的兩個成員變量：signum表示大數的符号，int數組mag[]表示大數的值，mag[0]表示大數的最高位

構造方法

通過byte[]數組構造

byte[]數組可以了解為整數在記憶體中的表示，如：

byte[] b = {0x81,0x00,0x00,0x00} // 在記憶體中即為0b10000001 00000000 00000000 00000000
           

由byte[]數組轉為大數，可以了解為将byte[]數組轉為一個占用 byte.length * 8 位的大整型，byte[]是該數的補碼

源碼如下：

public BigInteger(byte[] val) {
        if (val.length == 0)
            throw new NumberFormatException("Zero length BigInteger");

        if (val[0] < 0) {
            mag = makePositive(val);
            signum = -1;
        } else {
            mag = stripLeadingZeroBytes(val);
            signum = (mag.length == 0 ? 0 : 1);
        }
        if (mag.length >= MAX_MAG_LENGTH) {
            checkRange();
        }
    }
           

首先判斷byte[0]是正數還是負數，如果byte[0]是正數，則大數的符号位signum為1，mag值為byte[]去掉字首0；

否則大數的符号位為-1，此時mag的值是-val ，舉例如下

byte[] = {0b00001000,0b00000000}  最高位是0，表示正數, 轉為大數是它本身
signum = 1
mag[] = int[0] = 0b00001000_00000000 -> 4096

//
byte[] = {0b10001000,0b00000000}  最高位是1，表示負數，轉為大數是它的負值
signum = -1
mag[] = int[0] = 0b01111000_00000000 
           

Q：符号位存在的必要性？

指定符号位 BigInteger(byte[] bytes, int signum) 

當指定符号位時，無論指定1還是-1，mag[]值都是大數本身

位運算

分析之前先看一段關鍵代碼，getInt方法用于獲得一個大數中的每一個int的實際值，為什麼要這麼做？因為在構造的時候，根據符号位對mag[]的值做了轉換，而位運算需要對實際值的每一位做運算，是以要把取負的數再取負還原；

/**
 * 對于符号位為正的大數，mag[]傳回它本身，對于符号位為負的大數，由于在構造的時候對int值取了負，進行位運算要還原
**/
private int getInt(int n) {
        if (n < 0)
            return 0;
        if (n >= mag.length)
            return signInt();

        int magInt = mag[mag.length-n-1];

        return (signum >= 0 ? magInt :
                (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
}
           

再來看這段代碼 n <= firstNonzeroIntNum() ? -magInt : ~magInt

考慮當我們對一個數取負時做了什麼操作，答案是減一取反，那麼對每一個bit來說，從後往前看找到第一個非0的位，該位和它的後面的位實際上是減一取反（-），該位之前做的都是取反操作（～）

根據上述原理，firstNonzeroIntNum()方法會傳回mag[]從後往前第一個非0的index，該index左邊的數取反，右邊的數取負

按位與 and

public BigInteger and(BigInteger val) {
        int[] result = new int[Math.max(intLength(), val.intLength())];
        for (int i=0; i < result.length; i++)
            result[i] = (getInt(result.length-i-1)
                         & val.getInt(result.length-i-1));

        return valueOf(result);
}
           

按位取反 not

原理是按照符号位signum将mag[]數組的每個值取其實際值，然後對該值取反

public BigInteger not() {
        int[] result = new int[intLength()];
        for (int i=0; i < result.length; i++)
            result[i] = ~getInt(result.length-i-1);

        return valueOf(result);
}