Java BigInteger字符串转内部表示的算法疑问解析

我正在研究Java类库中BigInteger将字符串转换为内部数值表示的算法，核心代码片段如下：

// Pre-allocate array of expected size. May be too large but can
        // never be too small. Typically exact.
        long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
        if (numBits + 31 >= (1L << 32)) {
            reportOverflow();
        }
        int numWords = (int) (numBits + 31) >>> 5;
        int[] magnitude = new int[numWords];

        // Process first (potentially short) digit group
        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");

        // Process remaining digit groups
        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");
            destructiveMulAdd(magnitude, superRadix, groupVal);
        }
        // Required for cases where the array was overallocated.
        mag = trustedStripLeadingZeroInts(magnitude);
        if (mag.length >= MAX_MAG_LENGTH) {
            checkRange();
        }

针对这段代码的数学逻辑，以下是具体疑问的解答：

1. bitsPerDigit的含义是什么？调试时其值为3402，是否为Java中int类型中单个数字的占用位数？ #

bitsPerDigit是预计算的固定数组，对应不同进制下，单个数字所需二进制位数的1024倍近似值。你看到的3402是十进制对应的数值——因为log₂(10)≈3.3219，乘以1024后就约等于3402。它不是int类型中单个数字的实际占用位数，而是用来快速估算总二进制位数的缩放系数，目的是避免浮点运算，提升计算效率。

2. 为何将(numDigits * bitsPerDigit[radix])的结果执行无符号右移10位（即除以2^10）后加1？ #

因为bitsPerDigit是log₂(radix)×1024的近似值，所以numDigits * bitsPerDigit[radix]等价于总二进制位数×1024，右移10位就得到总二进制位数的近似值。加1是为了抵消近似值的误差，确保预分配的数组绝对不会太小——哪怕估算值比实际需求略小，加1后也能覆盖实际所需的位数。

3. 为何在将numBits无符号右移5位（即除以2^5=32）前要先加31？（我了解32是Java中int的位数） #

这是典型的向上取整除法技巧。每个int占用32位，我们需要计算存储numBits位二进制数需要多少个int。比如：

• 如果numBits是33位，33+31=64，64>>>5=2，正好需要2个int；
• 如果numBits是32位，32+31=63，63>>>5=1，刚好需要1个int。
  本质上就是(numBits + 32 - 1) / 32，用位运算代替除法，能大幅提升计算效率。

4. destructiveMulAdd是什么方法？它的工作原理是怎样的？ #

这是BigInteger内部的原地修改型乘法加法方法，名字里的"destructive"意思是直接修改传入的magnitude数组，不创建新数组。它的作用是：把当前magnitude数组表示的大数，先乘以superRadix（也就是radix^digitsPerInt[radix]，比如十进制下digitsPerInt是9，superRadix就是10⁹），再加上groupVal。实现上是模拟手工大数乘加的过程，逐位处理进位，保证运算在int数组中高效进行。

5. 这些算法是否有官方文档进行说明？ #

OpenJDK的BigInteger源码里只有零散的注释，没有专门的官方文档详细拆解这些底层算法。不过这些都是经典的大数处理技巧，你可以参考源码中的注释，或者OpenJDK源码仓库里的相关说明，另外不少大数运算的专业教材也会覆盖类似的分组转换、数组预分配技巧。

内容的提问来源于stack exchange，提问作者ng.newbie