Kotlin中BigInteger转任意进制字符串的性能问题排查与优化

DevOps 小满

2026-8-9

问题

需要在Kotlin中将超大正BigInteger（多达数千位）转换为指定进制（最高100或更高）的字符串。对于进制≤36的情况，可直接使用原生toString(base)方法，但针对更大进制，编写了如下扩展函数：

fun BigInteger.toStringX(base: Int): String {
    if (base <= 36) return toString(base)  // improve speed if base <= 36
    val bigBase = base.toBigInteger()
    var n = this
    val stringBuilder = StringBuilder()
    while (n > ZERO) {
        val div = n.divideAndRemainder(bigBase)
        stringBuilder.append(DIGITS[div[1].toInt()])
        n = div[0]
    }
    return stringBuilder.reverse().toString()
}

其中DIGITS是包含所有数位字符的字符串。目前原生toString方法的速度比自定义函数快一个数量级——例如转换约10000位数字时，原生方法耗时60ms，自定义函数耗时500ms。想知道为何自定义函数速度如此缓慢，并寻求在保留支持大于36进制能力的前提下优化速度的建议。另外，将append()替换为insert()并去掉最后一行的reverse()，性能提升并不明显。

原因分析

原生方法的底层优化：JDK的BigInteger.toString(base)基于底层优化实现，部分路径采用汇编级加速，针对大数字进制转换做了批量处理、内存分配优化等，而自定义函数是纯上层Kotlin代码，没有这类底层加速。
高频除法取余的开销：每次循环调用divideAndRemainder(bigBase)都会触发一次大整数除法运算，这是大整数操作中开销最高的步骤之一。原生方法采用分块计算的高效算法，一次性生成多个数位；而自定义函数逐位计算，数千位数字就要执行数千次除法，累计开销巨大。
字符串构建的额外损耗：虽然StringBuilder效率较高，但逐位append再reverse的操作，加上每次从DIGITS字符串中索引取字符的操作，相比原生方法直接在字符数组上批量填充的方式，多了一层不必要的开销。

优化建议

批量计算多位数字：不要每次只计算1位，而是计算能塞进Long范围的最大数位数量（比如base=100时，可一次计算9位，因为100^9=1e18 < 2^63）。先预计算bigBase^k（k为最大可行位数），通过divideAndRemainder得到高位部分和余数，再将余数转换为k位字符串（不足补前导零），这样能把循环次数降低到原来的1/k，大幅减少除法运算次数。
预计算幂次并从高位开始构建：提前计算bigBase的幂次直到超过原数大小，然后从最高位开始逐段计算，直接填充字符，避免reverse操作，同时减少循环中的重复计算。
直接操作字符数组：预先估算转换后的字符串长度，创建对应大小的字符数组，直接在数组中填充字符，规避StringBuilder的append/reverse带来的微小损耗。
优化字符索引访问：将DIGITS字符串转换为字符数组（val DIGITS_ARRAY = DIGITS.toCharArray()），数组的索引访问速度比字符串更快。
十进制字符串中转法：先将BigInteger转为十进制字符串，再批量将十进制字符串转换为目标进制字符串。这种方式的批量运算效率可能高于直接对BigInteger做除法取余。

内容的提问来源于stack exchange，提问作者Anypodetos