将大整数转换为不带模基数的字符串的算法

Question

我找了一段时间才找到一种将整数转换为字符串的算法。我的要求是手动执行此操作，因为我使用的是我自己的大数字类型。我定义了 + - */(with remainder) ，但需要找到一种方法来从 double int 打印单个数字(高和低，如果 int 是 64 位，则总共 128 位)。

我看过一些答案比如

Convert integer to string without access to libraries

Converting a big integer to decimal string

但想知道是否可以使用更快的算法。我愿意直接使用位(例如 base2 到 base10-string - 但是我找不到这样的算法)，但我只是希望避免重复除以 10 对于可能大到 2^128 的数字。

Answer 1

您可以使用分而治之的方式使用标准库将部分转换为字符串(这通常在该工作中非常有效)。

因此，不必在每次迭代中都除以 10，例如，您可以除以 10**15，然后让您的库将 block 转换为 15 位数字的字符串。最多完成三个步骤后，您就完成了。

当然，您必须对零填充进行一些字符串操作。但是也许你的图书馆也可以在这里帮助你，如果你对所有较低的部分使用类似 %015d 零填充格式，并且对于最高的非零部分使用非填充 %d 格式。