Java BigInteger的destructiveMulAdd方法与大端存储技术问询

我正在研究Java常用工具类的内部实现，重点关注BigInteger的内部存储机制。发现它通过int[]以大端（big-endian）格式存储数值量级，核心逻辑由destructiveMulAdd方法实现，代码如下：

private static void destructiveMulAdd(int[] x, int y, int z) {
        // Perform the multiplication word by word
        long ylong = y & LONG_MASK;
        long zlong = z & LONG_MASK;
        int len = x.length;

        long product = 0;
        long carry = 0;
        for (int i = len-1; i >= 0; i--) {
            product = ylong * (x[i] & LONG_MASK) + carry;
            x[i] = (int)product;
            carry = product >>> 32;
        }

        // Perform the addition
        long sum = (x[len-1] & LONG_MASK) + zlong;
        x[len-1] = (int)sum;
        carry = sum >>> 32;
        for (int i = len-2; i >= 0; i--) {
            sum = (x[i] & LONG_MASK) + carry;
            x[i] = (int)sum;
            carry = sum >>> 32;
        }
    }

调试总结的执行步骤 #

乘法阶段 #

1. 处理大数时，将其拆分为整数片段，与base10下值为10^9的superRadix一同传入该方法；
2. 方法内通过掩码将参数转换为long类型，避免符号位干扰计算；
3. 从量级数组的最后一位（最低位分段）开始，计算superRadix与数组元素的乘积并加上进位值；
4. 将乘积截断为int（仅保留64位long的低32位）存入数组对应位置；
5. 将乘积的高32位通过无符号右移32位得到新的进位值；
6. 重复上述操作直至遍历完数组首位。

求和阶段 #

1. 将原始片段（zlong）与数组最后一位元素相加得到sum；
2. 将sum截断为int存入数组最后一位；
3. 将sum无符号右移32位得到进位值；
4. 从数组倒数第二位开始向前遍历，重复截断存储和进位处理操作。

核心问题解答 #

问题1：该数组究竟以何种方式存储量级？ #

这个int[]数组是以superRadix为基数的大端分段存储：

• 数组的每个元素是数值的一个分段，取值范围在0到superRadix-1之间（比如superRadix为10^9时，每个元素是0~999999999的整数）；
• 数组索引越小，对应的分段权重越高（大端存储），比如数值1234567890123会被拆分为[1, 234, 567890123]，其中1对应1*10^12，234对应234*10^9，567890123对应567890123*10^0；
• 而destructiveMulAdd的作用是破坏性地执行x = x * y + z（直接修改传入的x数组），这里y就是superRadix，所以每次调用相当于把当前表示的数乘以基数，再加上新的低位分段z，以此逐步构建完整的大数。

问题2：这难道不应该是小端（little-endian）存储吗？ #

不是，要区分存储顺序和计算顺序：

• 大端存储的定义是「最高有效位（权重最高的分段）存放在数组的最低索引位置」，这和我们上面的例子一致；
• 计算时从数组最后一位（最低权重分段）开始，是因为乘法和加法的进位逻辑需要从低位到高位处理，这是运算的常规流程，和存储的端序无关。比如你手写加法也是从个位（最低位）开始算，不管数字是从左到右（大端）写还是从右到左（小端）写。

问题3：base10下superRadix设为10^9的原因是什么？ #

主要有三个核心原因：

1. 适配int的存储范围：int的最大值是2^31-1=2147483647，10^9=1000000000小于这个值，所以每个分段可以安全地用int存储，不会溢出；
2. 避免乘法溢出：两个10^9量级的int相乘，结果是10^18，刚好可以被64位的long完全容纳（long的最大值约为9e18），这样在计算乘积时可以用long临时存储，无需额外处理溢出，简化运算逻辑；
3. 十进制转换效率高：10^9是10的整数次幂，在将BigInteger和十进制字符串互相转换时，可以直接按每9位拆分/拼接，提升转换效率。

问题4：截断和移位操作实际是在做什么？是否等价于取模后除法？ #

是的，这两个操作完全等价于无符号的取模和除法：

• (int)product：将64位的long截断为32位int，等价于对2^32取模，因为只保留了低32位的数值；
• product >>> 32：无符号右移32位，等价于将product除以2^32取商，得到的就是进位值；
• 这里用& LONG_MASK（即0xffffffffL）将int转换为无符号long，是为了避免int的符号位影响计算，确保所有操作都是按无符号数值处理的。

问题5：整个destructiveMulAdd方法的完整执行逻辑是怎样的？ #

这个方法的核心是在原数组上直接修改，完成大数x = 大数x * y + z的计算，其中：

• x：用int数组表示的大数（大端分段存储，基数为y）；
• y：基数superRadix（比如10^9）；
• z：要添加的低位分段（0到y-1之间的整数）；

完整流程分两步：

1. 乘法阶段：从数组的最低位（最后一个元素）到最高位（第一个元素），依次计算每个分段与y的乘积，加上上一步的进位，将结果的低32位存回原位置，高32位作为新的进位传递到下一个高位；
2. 加法阶段：先把z加到数组的最低位，处理该位的进位，再从倒数第二位到最高位依次处理进位传递，更新每个分段的数值；
   整个过程没有创建新数组，直接修改传入的x数组，所以叫「destructive（破坏性）」方法。

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