algorithm - 二进制到十进制(大数)

Question

我正在构建一个基于大整数的 C 库。基本上，我正在寻找一种快速算法来将二进制表示中的任何整数转换为十进制数

我看到了 JDK 的 Biginteger.toString() 实现，但对我来说它看起来很沉重，因为它是用来将数字转换为任何基数的(它对每个数字使用除法，这应该在处理数千位数字时非常慢)。

因此，如果您有任何文档/知识可以分享，我很乐意阅读。

编辑:我的问题更精确:

• 设P为内存地址

• 令 N 为在 P 处分配(和设置)的字节数

如何将地址 P 处的 N 个字节表示的整数(假设为小端字节序以简化事情)转换为 C 字符串

例子:

• N = 1

• P = 存储 '00101010' 的一些随机内存地址

• 输出字符串 = "42"

还是谢谢你的回答

Answer 1

BigInteger.toString 方法看起来很重的原因是分块进行转换。

一个简单的算法会取最后一位数字，然后将整个大整数除以基数，直到没有剩余。

这样做的一个问题是大整数除法非常昂贵，因此将数字分割为可以使用常规整数除法(与 BigInt 除法相反)处理的 block :

static String toDecimal(BigInteger bigInt) {
  BigInteger chunker = new BigInteger(1000000000);
  StringBuilder sb = new StringBuilder();
  do {
    int current = bigInt.mod(chunker).getInt(0);
    bigInt = bigInt.div(chunker);
    for (int i = 0; i < 9; i ++) {
      sb.append((char) ('0' + remainder % 10));
      current /= 10;
      if (currnet == 0 && bigInt.signum() == 0) {
        break;
      }
    }
  } while (bigInt.signum() != 0);
  return sb.reverse().toString();
}

也就是说，对于固定基数，您可能会更好地移植“双重涉猎”算法以满足您的需求，如评论中所建议的:https://en.wikipedia.org/wiki/Double_dabble