二进制到十进制（大数）

Question

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

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

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

编辑：关于我的问题更精确：

设P一个内存地址
令N为在P

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

示例：

N=1
P = 一些随机内存地址存储'00101010'
out string = "42"

仍然感谢您的回答

Answer 1

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

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

一个问题是大整数除法非常昂贵，因此将数字细分为可以使用常规整数除法（与 BigInt 除法相反）处理的块：

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();
}

就是说，对于固定的基数，根据您的需要移植 "double dabble" 算法可能会更好，如评论中所建议：https://en.wikipedia.org/wiki/Double_dabble

Answer 2

我最近接受了打印一个大梅森素数的挑战：2**82589933-1。在我的 CPU 上，apcalc 需要大约 40 分钟，python 2.7 需要大约 120 分钟。这是一个2400万位的数字。

这是我自己的转换 C 代码：

// print 2**82589933-1

#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>

const uint32_t exponent = 82589933;
//const uint32_t exponent = 100;
//outputs 1267650600228229401496703205375
const uint32_t blocks = (exponent + 31) / 32;
const uint32_t digits = (int)(exponent * log(2.0) / log(10.0)) + 10;

uint32_t num[2][blocks];
char out[digits + 1];

// blocks : number of uint32_t in num1 and num2
// num1   : number to convert
// num2   : free space
// out    : end of output buffer
void conv(uint32_t blocks, uint32_t *num1, uint32_t *num2, char *out) {
  if (blocks == 0) return;
  const uint32_t div = 1000000000;
  uint64_t t = 0;
  for (uint32_t i = 0; i < blocks; ++i) {
    t = (t << 32) + num1[i];
    num2[i] = t / div;
    t = t % div;
  }
  for (int i = 0; i < 9; ++i) {
    *out-- = '0' + (t % 10);
    t /= 10;
  }
  if (num2[0] == 0) {
    --blocks;
    num2++;
  }
  conv(blocks, num2, num1, out);
}

int main() {
  // prepare number
  uint32_t t = exponent % 32;
  num[0][0] = (1LLU << t) - 1;
  memset(&num[0][1], 0xFF, (blocks - 1) * 4);
  // prepare output
  memset(out, '0', digits);
  out[digits] = 0;
  // convert to decimal
  conv(blocks, num[0], num[1], &out[digits - 1]);
  // output number
  char *res = out;
  while(*res == '0') ++res;
  printf("%s\n", res);
  return 0;
}

转换是破坏性的并且是尾递归的。在每一步中，它将 num1 除以 1_000_000_000，并将结果存储在 num2 中。余数加到out。然后它用 num1 和 num2 切换并经常缩短一个（blocks 递减）来调用自己。 out从后往前填。您必须将其分配得足够大，然后去除前导零。

Python 似乎正在使用类似的机制将大整数转换为小数。

想要做得更好？

对于像我这样的大数字，每次除以 1_000_000_000 需要相当长的时间。在一定规模下，分而治之算法会做得更好。在我的例子中，第一个除法是除以 10 ^ 16777216 将数字分成被除数和余数。然后分别转换每个部分。现在每个部分仍然很大，所以再次拆分为 10 ^ 8388608。递归地继续拆分直到数字足够小。每个可能说 1024 位数字。那些使用上面的简单算法转换的。必须测试“足够小”的正确定义，1024 只是一个猜测。

虽然两个大整数的长除法很昂贵，但比除以 1_000_000_000 更昂贵，因此节省了花费的时间，因为每个单独的块需要除以 [=35= 的次数要少得多] 转换为十进制。

而且，如果您已将问题拆分为单独且独立的块，则离将块分散到多个核心之间只有一小步之遥。那将真正加快转换的另一个步骤。看起来 apcalc 使用分而治之但不是多线程。

二进制到十进制（大数）

Binary to decimal (on huge numbers)

algorithm

binary

decimal

biginteger