3

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

背景

在 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 为底的值开始。所以问题是“如果无法知道那个值是什么，你如何将除数初始化为最大可能的 base10 值？”

我试过的

仍在尝试起草解决方案。

研究

我在这里找到的一些链接包括以下内容：

将“大”十六进制数（字符串格式）转换为没有 BigInteger 类的十进制数（字符串格式）

C：以 10 为底打印一个 BigInteger

将 BigInteger 转换为十进制（Base 10）字符串的最快方法？

将“大”十六进制数（字符串格式）转换为没有 BigInteger 类的十进制数（字符串格式）

谷歌搜索发现了其他东西，但没有什么能具体回答我的问题。

想法

我认为可能有效的一种方法如下（在伪代码中）：

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 位置除以两次。一个用于实际除法，另一个用于除数。

4

4 回答 4

4

一种（相当常见的）方法，无论是对于大整数还是普通整数类型，都是重复将数字除以 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 = '\0'; // 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 位 - 略少），您可以估计输出所需的大小。

于 2016-06-04T18:08:36.870 回答
1

接受的答案已经为您提供了一种简单的方法来做到这一点。这很好用，给你一个很好的结果。但是，如果您确实需要将较大的值转换为字符串，则有更好的方法。

我就不赘述了，因为我的解决方案是用Delphi写的，很多读者不容易读懂，而且很长（100多行代码中的几个函数，使用其他函数等等。用一个简单的答案解释，特别是因为转换以不同的方式处理一些不同的数字基数）。

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

然后将部分转换“连接”（实际上，数字直接放在正确地址的单个缓冲区中），所以最后，你会得到一大串数字。

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

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

缓冲区的大小可以预先计算，通过执行类似的操作

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

我为不同的数字基数使用了一个预先计算的表，但这是一个实现细节。

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

参看。Brent, Zimmermann，“现代计算机算术”，算法 1.26

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

于 2016-06-12T01:33:51.650 回答
0

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

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++，我刚刚意识到 qustion 是关于 C 的，但仍然想将代码留在这里，也许是为了说明想法）

于 2016-08-04T14:15:03.160 回答
-1

这是正确的方法吗？

第二种方法不适用于 C 中的所有整数值。if divisor < dividend依赖于创建divisor大于（或等于）的 10 的幂dividend。由于大多数整数系统具有有限范围，因此不可能创建大于（或等于）dividend时的 10 的幂。dividend == INTEGER_MAX（除非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) = '\0';
}

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

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

于 2016-06-04T22:01:09.010 回答