将大整数转换为十进制字符串

Question

冒着让这个问题被投票为重复问题，甚至关闭它的风险，我提出了这个问题。

背景

在"normal"数据类型中，如int、long long等...，要将二进制数值转换为十进制字符串，您将执行以下操作（伪代码）：

Set length = 0
Set divisor to largest base10 value the data type will hold (Divisor).
  Loop
    Divide number in question by divisor.
    Place result in a string at position length.
    Increment the length by 1.
    Divide the divisor by 10.
Reverse the string.
Print the string.

（大多数）任何语言的实际实现都非常简单。

问题

我在使用上述方法时遇到的问题是，对于大整数（也称为任意精度算术），没有以 10 为底的最大值作为起始值.所以问题是"How do you initialize the divisor to the largest possible base10 value if there is no way to know what that value is?"

我试过的

仍在尝试起草解决方案。

研究

我在这里找到的一些链接包括：

Convert a "big" Hex number (string format) to a decimal number (string format) without BigInteger Class

C: print a BigInteger in base 10

Fastest way to convert a BigInteger to a decimal (Base 10) string?

Convert a "big" Hex number (string format) to a decimal number (string format) without BigInteger Class

Google 搜索找到了其他内容，但没有任何内容可以具体回答我的问题。

想法

我认为可能工作的一种方法如下（伪代码）：

Define p_divisor as previous divisor.
Set divisor = 1
  Loop:
    if divisor < dividend
      then
        Set p_divisor = divisor
        divisor = divisor * 10
      else
        end loop
  Loop:
    Divide number in question by divisor.
    Place result in a string at position length.
    Increment the length by 1.
    Divide the divisor by 10.
    if divisor == 1 then end loop
Reverse the string.
Print the string.

这是正确的方法吗？我有一个很大的整数库正在运行（包括乘法和除法），所以实现它并不难。我看到这种方法的最大问题是性能，因为你必须运行一个乘法序列来获得初始除数，然后你必须为每个 base10 位置除以两次。一个用于实际除法，另一个用于除数。

Answer 1

无论是大整数还是普通整数类型，一种（相当常见的）方法是将数字重复除以 10，将余数保存为下一位（从最低有效位开始）。继续前进，直到数字达到零。由于找到的第一个数字是最不重要的，因此您可能需要在末尾反转字符串，或者在进行时反向构建它。

使用普通 unsigned int 的示例可能如下所示：

void printUInt(unsigned x) {
  char buf[(sizeof(x) * CHAR_BIT) / 3 + 2]; // slightly oversize buffer
  char *result  = buf + sizeof(buf) - 1; // index of next output digit

  // add digits to result, starting at 
  //   the end (least significant digit)

  *result = '[=10=]'; // terminating null
  do {
    *--result = '0' + (x % 10);  // remainder gives the next digit
    x /= 10;
  } while (x); // keep going until x reaches zero

  puts(result);
}

这个过程对于一个大整数来说几乎是一样的——尽管如果可以的话，最好做除法并一步求出余数。

上面的示例从缓冲区的末尾构建字符串（因此 result 最终指向缓冲区中间的某处），但您也可以从头开始构建它，然后将其反转。

如果您可以确定原始数字中使用的位数（大约每 3 位增加 1 个数字——略少），则可以估计输出所需的大小。

Answer 2

Would this be the correct way?

第二种方法不适用于 C 中的所有整数值。if divisor < dividend 依赖于将 divisor 创建为大于（或等于）dividend 的 10 的幂。由于大多数整数系统的范围都是有限的，因此当 dividend == INTEGER_MAX 不可能时，创建大于（或等于）dividend 的 10 的幂。（除非 INTEGER_MAX 是 10 的幂）。

递归方法的工作原理是重复除以 10 并推迟数字分配，直到确定更重要的数字。当目标缓冲区的大小未知但足够大时，这种方法很有效。

以下句柄已签名 int，也适用于 INT_MIN，没有未定义的行为。

// Return location of next char to write
// Note: value is expected to be <= 0
static char *itoa_helper(char *s, int value) {
  if (value/10) {
    s = itoa_helper(s, value/10);
  }
  *s = '0' - value % 10;  // C99
  return s+1;
}

void itoa(int n, char *s) {
  if (n < 0) {
    *s++ = '-';
  } else {
    n = -n;
  }
  *itoa_helper(s, n) = '[=10=]';
}

#define INT_SIZEMAX  ((CHAR_BIT*sizeof(int) - 1)*28/93 + 3)
char buf[INT_SIZEMAX];
itoa(INT_MIN, buf);

此代码不是将负数转换为正数，而是相反，因为 -INT_MIN 在大多数系统上都失败。

Answer 3

接受的答案已经为您提供了一种简单的方法来执行此操作。这工作正常，给你一个很好的结果。但是，如果您确实需要将大值转换为字符串，则有更好的方法。

我就不细说了，因为我的解决方案写在Delphi里面，很多读者看不懂，而且很长（100+行代码里的几个函数，还没用其他功能等无法用简单的答案来解释，特别是因为转换以不同的方式处理一些不同的数字基数）。

但原则是将数字分成两个几乎相等大小的两半，一个数字是 10 的幂。要转换这些，递归地再次将它们分成两个较小的部分，按较小的 10 的幂，等等，直到零件的大小达到某种下限（例如，32 位），然后您最终将其转换为传统方式，即像接受的答案一样。

然后部分转换为"concatenated"（实际上是将数字直接放入正确地址的单个缓冲区中），所以最后得到一串巨大的数字。

这有点棘手，我只为那些想要调查这个非常大的数字的人提到它。对于少于 100 位的数字没有意义。

这确实是一种递归方法，但不是简单地除以 10 的方法。

可以预先计算缓冲区的大小，方法如下

bufSize = myBigInt.bitCount() * Math.log10(2) + some_extra_to_be_sure;

我对不同的基数使用预先计算的 table，但这是一个实现细节。

对于非常大的数字，这将比重复除以 10 的循环快很多，特别是因为那样，整个数字必须一直除以 10，而且它只会非常缓慢地变小。分而治之算法只会划分越来越小的数字，并且切割部分的（昂贵的）划分总数要低得多（我猜是 log N 而不是 N）。因此（平均而言）更小的数字上的划分更少。

比照。布伦特、齐默尔曼，"Modern Computer Arithmetic"，算法 1.26

我的代码和解释可以在这里找到，如果你想看看它是如何工作的：BigIntegers unit

Answer 4

我遇到了类似的问题，但没有找到我喜欢的解决方案，所以想出了我的 owm。这个想法是将你使用任何基数的 BigInt 转换为另一个基数为 10 的 BigInt，尽可能大但仍然小于你当前的基数。您可以使用系统调用通过 "digit" 进行转换，然后连接结果。所以从来没有涉及过明确的划分，只是隐藏在系统库函数中。总体复杂性仍然是二次方的（就像其他基于除法的解决方案一样）。

friend std::ostream& operator<<(std::ostream& out, const BigInt_impl& x){
    using Big10 = BigInt_impl<char32_t, uint64_t, 1000000000>; // 1e9 is the max power of 10 smaller then BASE
    auto big10 = Big10(0);
    auto cm = Big10(1);
    for(size_t i = 0; i < x.digits.size(); ++i, cm *= BASE){
        big10 += cm*x.digits[i];
    }
    out << big10.digits.back();
    for(auto it = next(big10.digits.rbegin()); it != big10.digits.rend(); ++it){ 
        out << std::setfill('0') << std::setw(9) << *it;
    }
    return out;
}

注意这个解决方案中的魔法常量 1e9 - 这仅适用于我的 BASE = 2^32。懒得好好做。

（对不起，对于 C++，我刚刚意识到问题是关于 C 的，但仍然想在这里留下代码，也许作为想法的说明）

将大整数转换为十进制字符串

Converting a big integer to decimal string

c

biginteger

format-conversion

bigint