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

EN

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

因此，与其在每次迭代中除以10，您还可以将代码块除以10**15，并让库将这些块转换为15位数字字符串。最多三步之后，你就完蛋了。

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

您可以尝试您的运气与一个人为的方法，如下所示。

数字可以用二进制编码的十进制表示来表示.在这种表示法中，每个十进制数字都存储在4位上，当执行加法时，如果两位数之和超过9，则添加6并向左进位。

如果您预先存储了所有2的幂的BCD表示，那么它最多需要128个加法来执行转换。您可以节省一点，因为对于低功耗，您不需要全长度加法(39位数)。

但这听起来像是很多行动。您可以通过将几个BCD数字打包成一个整数来“并行”它们: 32位上的整数加法相当于同时添加8位BCD数字。但我们的运货有问题。为了解决这一问题，我们可以将数字存储在5位而不是4位上，而携带将出现在第5位中。然后，我们可以通过掩蔽获得携带，将它们添加到下一个数字(移位左5)，并调整数字和(乘以10并减去)。

  2 3 4 5 6
+ 7 6 9 2 1
= 9 913 7 7

携带：

 0-0-1-0-0

调整：

  9 913 7 7
-0000010000
= 9 9 3 7 7

实际上，你必须处理可能的级联携带，所以和将涉及两个加数，并进行，并生成一个和并执行。

32位操作允许您一次处理6位数字(3 9位位7轮)，64位操作12位数(4轮39位数)。

1. 如果只想将数字编码为字符串，则为。 使用快速的十六进制数字，因为您可以通过位操作来转换所有数字.此外，使用Base64，编码也是可行的，只需通过位操作+转换表即可完成。Booth表示只能在O(n)中用小整数表示，其中n是打印数字的计数。
2. 如果你需要base10 然后打印一个十六进制字符串，并将其转换为十进制字符串，如下所示：

- [str\_hex2dec](https://stackoverflow.com/a/18231860/2521214)

这比#1慢得多，但在小整数算法上仍然可行.您也可以使用dec2hex进行反向操作(从字符串输入数字).

对于bigint库，还有另一种简化字符串/整数转换的方法：

1. BCD 二进制编码十进制..。打印为十六进制的数字是十进制数字。所以每个数字都有4位。这浪费了一些内存，但许多CPU都支持BCD，并且可以对这些整数进行本机操作。
2. 10^n 碱 有时使用基本10^n而不是2^m，而 10^n <= 2^m m是原子整数的位宽，n i是适合它内部的十位数。 例如，如果您的原子无符号整数是16位，那么它可以在基本的65536中保持2值。如果您使用基本的10000，您可以打印每个原子，从左开始使用零值作为十进数，然后将所有这样的打印叠加在一起。 这也浪费了一些内存，但通常不会浪费太多(如果位宽被合理选择)，您可以对整数使用标准指令。只有传送带才会有一点变化。 例如，对于32位单词： 2^32 = 4294967296 >= 1000000000 所以我们每32位浪费log2(4.2949...) = ~2.1比特。这比BCD log2(16/10)*(32/4)= ~5.42比特要好得多，而且通常更好地使用更高的比特宽度。