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

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

我看到了一些答案，比如

将整数转换为字符串而不访问库

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

但想知道是否有可能采用更快的算法。我对直接使用比特持开放态度(例如，从2到10的字符串-但我找不到这样的算法)，但我只是希望避免对可能大到2^128的数字重复除以10。

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

因此，您不需要在每次迭代中除以10，而是可以例如除以10**15，并让您的库将块转换为15位字符串。最多走三步，你就完了。

当然，您必须对零填充进行一些字符串操作。但是，如果您对所有较低部分使用%015d零填充格式，而对最高非零部分使用非填充%d格式，那么您的库在这方面也可能对您有所帮助。

您可以尝试一种人工方法，如下所示。

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

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

但这听起来像是很多操作。您可以通过将几个BCD数字封装在一个整数中来"并行化"它们：32位上的整数相加相当于8个BCD数字同时相加。但我们的搬运有问题。为了解决这个问题，我们可以将数字存储在5位而不是4位，进位将出现在第五位。然后，我们可以通过掩码获得进位，将它们与下一个数字相加(向左移动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位数字(39位为7轮)，64位操作，12位(39位4轮)。

如果您只想将数字编码为字符串

使用hex数字，这很快，因为您可以通过位运算来强制转换所有数字。。。使用Base64编码也可以通过位操作+转换表来实现。Booth表示只能在O(n)中对小整数进行，其中n是打印数字的计数。
如果您需要base10

然后打印十六进制字符串，并将其转换为十进制字符串，如下所示：
- str_hex2dec
这比#1慢得多，但在小整数上仍然可行。。。您也可以使用dec2hex反向执行此操作(从字符串中输入数字)。。。

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

BCD

二进制编码的十进制。。。打印为十六进制的数字是十进制数字。所以每个数字有4位。这浪费了一些内存，但许多CPU都支持BCD，并且可以在本机对此类整数进行操作。
基本10^n

有时使用基于10^n而不是2^m，而
```
10^n <= 2^m
```
m是原子整数的位宽，n是其中的十进制数字
例如，如果原子无符号整数是16位，则它可以在基2中容纳多达65536的值。如果你使用基数10000，你可以从左起用零垫将每个原子打印成十进制数，并简单地将所有这些打印结果叠加在一起。
这也会浪费一些内存，但通常不会太多(如果位宽选择合理)，并且可以对整数使用标准指令。只有进位传播会有一点变化。。。
例如，对于32位字：
```
2^32 = 4294967296 >= 1000000000
```
因此我们每32个比特浪费CCD_ 15个比特。这比BCDlog2(16/10)*(32/4)= ~5.42比特好得多，而且通常在比特宽度更高的中更好

相关内容

最新更新

热门标签：