Java大数源码剖析(四) - 1.位运算

发表于 更新于 阅读次数：

Java大数源码剖析(四) - 1.位运算

BigInteger提供的位操作

  • 按位与 : public BigInteger and(BigInteger val)
  • 按位与上对方的非 : public BigInteger andNot(BigInteger val)
  • 按位或 : public BigInteger or(BigInteger val)
  • 按位异或 : public BigInteger xor(BigInteger val)
  • 按位非 : public BigInteger not()

使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Test {
    public static void main(String[] args) {
        BigInteger x = new BigInteger("01011100110", 2); // 二进制构建大整数
        BigInteger y = new BigInteger("-1001001", 2);

        System.out.printf("x & y = %s\n", x.and(y).toString(2));
        System.out.printf("x & !y = %s\n", x.andNot(y).toString(2));
        System.out.printf("x | y = %s\n", x.or(y).toString(2));
        System.out.printf("x ^ y = %s\n", x.xor(y).toString(2));
        System.out.printf("!x = %s\n", x.not().toString(2));

    }
}
1
2
3
4
5
6
输出结果 :
x & y = 1010100110
x & !y = 1000000
x | y = -1001
x ^ y = -1010101111
!x = -1011100111

注意 : 位运算全部是按补码形式进行的操作, 譬如示例中-1001001的补码是10110111

实现思路

注意到位运算是按照补码形式的二进制进行的, 但是BigInteger里面存放的是绝对值的二进制。对于正数来说，补码的二进制形式与其绝对值的二进制形式是一致的；但是对于负数来说，是不相同的，所以JDK中提供了一个方法（int getInt(int n)）用来获取补码的第n个int对应的二进制形式，n是从低位也就是mag数组尾部以0开始计数的。比如正数0x66ABCDEFFF的第0个int就是ABCDEFFFF。

现在还有一个问题，位运算是按二进制进行的运算，如果两个操作数的位数不相同怎么办，JDK里是这样处理的，正数高位补0，负数高位补1，getInt的参数n就算是大于mag数组的长度也可以获取到值（正数获取到0，负数获取到-1也就是0xFFFFFFFF）。

现在有了这个getInt方法，对于每一种运算的不同就只有获取到对应位置的int后如何处理了，将每一对int的运算结果依此存入结果数组的对应位置就会得到一个int数组表示位运算的结果。

值得注意的是，最终得到的结果数组是补码形式的, 所以还需要将其转换为绝对值的二进制, JDK提供了private static BigInteger valueOf(int val[])根据补码构造BigInteger

根据上面的分析, 我们可以得出位操作的代码都是大同小异的, 事实上JDK中的源码的确如此, 它们的源码非常相似(特别地, not方法中result的大小直接为自己的intLength(),并且无需参数)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// op表示不同的位操作符, 它们实在是太类似了, 使用C/C++编写甚至可以利用宏生成代码
public BigInteger func(BigInteger val) {
    
    // 分配一个数组用来存放结果(补码形式的)
    int[] result = new int[Math.max(intLength(), val.intLength())];  // intLength方法
    for (int i=0; i < result.length; i++)  // 计算result的每一个元素    // 返回补码二进制
        result[i] = (getInt(result.length-i-1)                       // 需要几个int来存
                     op val.getInt(result.length-i-1));

    return valueOf(result);  // 利用补码构造BigInteger
}

// 比如, or操作的源码形式就是这样
public BigInteger or(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);
}

下面剖析三个核心函数的源码 :

  • 获取大整数的二进制补码形式(包括符号位)要用几个int才能存下 : private int intLength()
  • 获取大整数二进制补码形式的第$32n$到第$32(n+1)-1$位, 用int存放结果 : private int getInt(int n)
    • 第$i$位是指从低字节到高字节方向的从0开始计数的第$i$个二进制位
    • 如果n超过大整数mag数组的长度, 结果与符号有关, 为正则返回0, 为负则返回-1(也就是0xFFFFFFFF)
  • 利用补码构造大整数 : private static BigInteger valueOf(int val[])

剖析private int intLength()

源码 : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Returns the length of the two's complement representation in ints,
 * including space for at least one sign bit.
 */
/**
 * 返回二进制补码形式以int的长度分组后的组数, 包含符号位的位置.
 * (实在没有想到的更自然的翻译@_@)
 */
private int intLength() {
    // 补码二进制形式(不包含符号位)长度 / 32 + 1
    // 除以32好理解, +1是为了给符号位留一个空间
    // 	(可以整除则说明正好用完所有int, 符号位需要一个新的int来存, 需要+1(加上新的int))
    // 	(不可整除说明最后一个int没用完, 符号位存在最后一个没用完的int中就可, 
    //   也需要+1(加上由于整除舍去的那个int))
	return (bitLength() >>> 5) + 1;  // bitLength : 获取二进制补码形式长度(不包含符号位)
}

可见, 在intLength中又调用了bitLength(获取二进制补码形式长度(不包含符号位))

bitLength源码 :

  • 分析
    • 为零 : 0
    • 正数 : 二进制形式的长度(去除前导0)
    • 负数 : 二进制形式的长度(去除前导0), 特别地, 如果是负的2的幂, 则mag数组最高的二进制位的1同时也是符号位, 所以为了去除符号位后需要将长度减一。
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
/**
 * Returns the number of bits in the minimal two's-complement
 * representation of this BigInteger, <em>excluding</em> a sign bit.
 * For positive BigIntegers, this is equivalent to the number of bits in
 * the ordinary binary representation.  For zero this method returns
 * {@code 0}.  (Computes {@code (ceil(log2(this < 0 ? -this : this+1)))}.)
 *
 * @return number of bits in the minimal two's-complement
 *         representation of this BigInteger, <em>excluding</em> a sign bit.
 */
/**
 * 返回这个BigInteger对应二进制补码形式中除去符号位后的二进制位的个数
 * 对于正的大整数, 结果和平凡的二进制形式的长度相同, 对于0直接返回0
 */
public int bitLength() {
    int n = bitLengthPlusOne - 1;  // 懒惰求值, bitLengthPlusOne初始化为0
                                   // 存放bitLength + 1的值；
                                   // 如果n != -1则说明已经求过了, 直接
                                   // 返回n即可。
    if (n == -1) {  // 没有求值过
        int[] m = mag;
        int len = m.length;
        if (len == 0) {
            // 由于mag数组规定是没有前导0的, 所以len == 0就说明这个大整数是0
            n = 0;
        }  else {
            // 计算mag数组二进制形式下的长度, 长度是清除二进制形式下的前导0后的结果
            // 计算 : len - 1个int所用的二进制位的个数 + 
            //       最高位int除去二进制下的前导0后的二进制位的个数
            //
            /// 比如设mag = {7, 10} => 0000,0007,0000,000A => 长度 : 32 + 3 = 35
            int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
             if (signum < 0) {  // 如果是负数则需要判断是否为负的2的幂
                 
                 // Check if magnitude is a power of two
                 boolean pow2 = (Integer.bitCount(mag[0]) == 1);
                 for (int i=1; i< len && pow2; i++)
                     pow2 = (mag[i] == 0);
				
                 // 如果是负的2的幂, 则mag数组最高的二进制位的1同时也是符号位, 
                 // 所以为了去除符号位后需要将magBitLength减一
                 n = (pow2 ? magBitLength - 1 : magBitLength);
             } else {  // 对于正的大整数, 结果就是n
                 n = magBitLength;
             }
        }
        bitLengthPlusOne = n + 1;  // 缓存结果到bitLengthPlusOne
    }
    return n;
}

辅助方法说明 : 

1
2
3
4
5
// 获取一个int去除二进制形式下的前导零后的二进制位的个数
static int bitLengthForInt(int n) {
    // int numberOfLeadingZeros(int n) : 获取n二进制形式下前导0的个数
    return 32 - Integer.numberOfLeadingZeros(n);
}

剖析private int getInt(int n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 获取大整数二进制补码形式的第32n到第32(n+1)-1位, 用int存放结果`
 * (第i位是指从低字节到高字节方向的从0开始计数的第i二进制位)
 */
private int getInt(int n) {
    if (n < 0)
        return 0;
    if (n >= mag.length)  // 如果n比mag的长度还大, 直接根据符号返回0或-1(0xFFFFFFFF)
        return signInt();

    int magInt = mag[mag.length-n-1]; // 第n个int对应在mag数组中的int

    return (signum >= 0 ? magInt :  // 如果是正数或0则本身就是补码, 直接返回即可
            (n <= firstNonzeroIntNum() ? -magInt : ~magInt)); // 否则需要转换为补码
}

负数情况下最后对magInt处理的详细说明 :

将原码转换为补码的常见做法是取反加1, 如果将原码二进制按固定大小分组后, 补码的每一组又该如何从原码的每一组获取呢?

假设以4位为一组分组

符号位 第3组 第2组 第1组 第0组
原码 1 0101 1010 1101 0000
补码 1 1010 0101 0011 0000

可见, 补码形式下的第2, 3组只需将原码取反即可；而第1组需要取反再加1, 第0组怎么处理都行

而取反加1其实就是取负

所以 : 负数情况下需要将magInt做如下处理后再返回

  • 如果组号比较小, 小于第一个有非0bit的组的组号, 怎么处理都行, 反正是0, JDK原码将其归为了下面一种情况处理；

  • 如果组号等于第一个有非0bit的组的组号，则需要将magInt取负后返回；

  • 如果组号比较大，直接将magInt取反后返回。

剖析private static BigInteger valueOf(int val[])

根据符号位判断是正是负, 构造BigInteger

源码 :

1
2
3
4
private static BigInteger valueOf(int val[]) {
    // 根据补码判断正负, 如果为正直接构造, 为负调用根据补码构造
    return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
}

核心方法(直接构造):

1
2
3
4
5
6
7
BigInteger(int[] magnitude, int signum) {
    this.signum = (magnitude.length == 0 ? 0 : signum);
    this.mag = magnitude;
    if (mag.length >= MAX_MAG_LENGTH) {
        checkRange();
    }
}

核心方法(根据补码构造):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private BigInteger(int[] val) {
    if (val.length == 0)
        throw new NumberFormatException("Zero length BigInteger"); // check

    if (val[0] < 0) { // val[0] < 0 => val[0]为负数 => val[0]的二进制形式最高位为1 =>
                      // 以val为补码表示的整数为负数
        mag = makePositive(val);  // 调用makePositive将补码val变成原码(不包含符号位)
        signum = -1;
    } else {
        mag = trustedStripLeadingZeroInts(val);  // 去除前导0
        signum = (mag.length == 0 ? 0 : 1);
    }
    if (mag.length >= MAX_MAG_LENGTH) {
        checkRange(); // check
    }
}

private BigInteger(int[] val)的核心是makePositive方法:

我的评价 : 此方法的实现有偷懒之嫌, 直接机械的利用取反加1, 实际上有更高效的方法, 和getInt采用的算法类似

我的思路 :

  • 从数组的后向前找第一个不是0的int, 将其取负, 然后再向前继续遍历, 将每个int取反直到遍历到最后一个不是先导1的int为止(最朴素的手算算法)
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
private static int[] makePositive(int a[]) {
    int keep, j;

    // 略过所有因为补码有符号扩展多出来的二进制1, 表现为int就是-1(0xFFFFFFFF)
    for (keep=0; keep < a.length && a[keep] == -1; keep++)
        ;

    // 看看是不是除了前导1剩下的全是0, 如果全是0则对应于补码表示的是负的2的幂的情况
    // 转换为真值后需要的空间比去除符号位后的补码还要多一个
    // 比如 : 补码1,0000 =真值=> -10000 占用5个二进制位
    // 而     补码1,0100 =真值=> -1100  只需占用4个二进制位
    for (j=keep; j < a.length && a[j] == 0; j++)
        ;
    
    int extraInt = (j == a.length ? 1 : 0); // 如果是上述情况则需多分配一个int
    int result[] = new int[a.length - keep + extraInt];

    // 取反
    for (int i = keep; i < a.length; i++)
        result[i - keep + extraInt] = ~a[i];

    // 加一
    // ++result[i] == 0是为了判断是否有进位, 如果==0则说明有进位需要进一步的将高位加1
    for (int i = result.length - 1; ++result[i] == 0; i--)
        ;

    return result;
}

根据我的思路改编的makePositive : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static int[] makePositive_PGZXB(int a[]) {
    int scan = 0;
    int j = 0;

    for (scan = 0; scan < a.length && a[scan] == -1; scan++);

    for (j = scan; j < a.length && a[j] == 0; j++);

    int exIdx = (j == a.length ? 1 : 0);
    int result[] = new int[a.length - scan + exIdx];

    int i;
    for (i = a.length - 1; i >= Math.max(scan - 1, 0) && a[i] == 0; i--);

    result[i - scan + exIdx] = -a[i];

    for (i--; i >= scan; i--) result[i - scan + exIdx] = ~a[i];

    return result;
}

不知道最新的官方JDK里这个方法有没有被改进@w@~~