将大整数转换为十进制字符串 [英] Converting a big integer to decimal string

问题描述

冒着将这个问题重复表决甚至关闭的风险，我想出了这个问题.

At the risk of having this question voted as a duplicate, or even to have it closed, I had this question has come up.

背景

在普通"数据类型(例如int，long long等)中，要从二进制数值转换为十进制字符串，您将执行以下操作(以伪代码):

In "normal" data types such as int, long long, etc..., to convert from the binary numeric value to a decimal string, you would do the following (in pseudo code):

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.

(大多数)任何语言中的实际实现都是微不足道的.

The actual implementation in (most) any language is quite trivial.

问题

上述方法遇到的问题是，对于大整数(也称为任意精度算术)，没有最大的以10为底的值.因此，问题是如果无法知道该值是多少，如何将除数初始化为可能的最大base10值?"

The issue that I am encountering with the above method is that with big integer numbers (also known as arbitrary precision arithmetic), there is no largest base 10 value to start with. So the question is "How do you initialize the divisor to the largest possible base10 value if there is no way to know what that value is?"

我尝试过的事情

仍在尝试草拟解决方案.

Still trying to draft a solution.

研究

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

Some of the links that I have found here include the following:

转换一个大"的没有BigInteger类的十六进制数字(字符串格式)到十进制数字(字符串格式)

C:以10为底打印BigInteger

最快的方式来转换BigInteger转换为十进制(Base 10)字符串?

转换一个大"的没有BigInteger类的十六进制数字(字符串格式)到十进制数字(字符串格式)

Google搜索发现了其他问题，但是没有什么可以专门回答我的问题.

A Google search turned up other things, but nothing that specifically answers my question.

想法

我认为可能起作用的一种方法如下(使用伪代码):

One method that I think that might work is as follows (in pseudo code):

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

Would this be the correct way? I have a big integer library up and working (including multiplication and division) so it wouldn't be that hard to pull this off. The big issue that I see with this method is performance, because you have to run a multiplication sequence to get the initial divisor, then you have to divide twice for each base10 position. One for the actual division, and the other for the divisor.

推荐答案

不管是大整数还是普通整数类型，一种(相当普遍的)方法是将数字重复除以10，并将余数保存为下一位(从最低有效位开始).继续前进，直到数字达到零为止.由于找到的第一位数字的最低位，您可能需要在字符串的末尾反转，或者在进行时反向构建.

One (fairly common) way to do this, whether for big integer or normal integer types, is to repeatedly divide the number by 10, saving the remainder as the next digit (starting with the least significant). Keep going until the number reaches zero. Since the first digit found is the least significant, you may need to reverse the string at the end, or build it in reverse as you go.

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

An example using ordinary unsigned int might look like:

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

对于一个大整数，该过程几乎相同-尽管如果可以的话，最好是一步除法并找到余数.

The process is pretty much the same for a big integer -- though it would be best to do the division and find the remainder in one step if you can.

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

The above example builds the string from the end of the buffer (so result ends up pointing in the middle of the buffer somewhere), but you could also build it from the start and reverse it afterward.

如果可以确定原始数字中使用的位数(每3位大约增加1位-少一点)，则可以估计输出所需的大小.

You can estimate the size needed for the output if you can determine the number of bits used in your original number (about 1 additional digit per 3 bits -- slightly less).

这篇关于将大整数转换为十进制字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！