将大整数转换为不带模基数的字符串的算法
Algorithm for Converting large integer to string without modulo base
我找了一段时间想找到一种将整数转换为字符串的算法。我的要求是手动执行此操作，因为我使用的是我自己的大数字类型。我已经定义了 + - * /(with remainder)，但需要找到一种方法来从 double int 打印单个数字（高和低，如果 int 是 64 位，则总共 128 位）。
我看到了一些答案，例如
Convert integer to string without access to libraries
但想知道是否可以使用更快的算法。我愿意直接使用位（例如 base2 到 base10-string - 但是我找不到这样的算法），但我只是希望避免重复除以 10 对于可能大到 2^128 的数字。
您可以使用分而治之的方式使用您的标准库将部分转换为字符串（这通常在该工作中非常有效）。
因此，不必在每次迭代中都除以 10，例如，您可以除以 10**15，然后让您的库将块转换为 15 位数字的字符串。最多三步后，你就完成了。
当然，您必须对零填充进行一些字符串操作。但是也许你的图书馆也可以在这里帮助你，如果你对所有较低的部分使用类似 %015d 零填充格式，并且对于最高的非零部分使用非填充 %d格式。
你可以用一个人为的方法试试你的运气，如下。
可以使用二进制编码的十进制表示法来表示数字。在这种表示中，每个小数位存储在4位上，并且在执行加法时，如果两位数之和超过9，则加6并向左进位。
如果你预先存储了2的所有次方的BCD表示，那么最多需要128次加法来进行转换。您可以节省一点，因为对于低幂，您不需要全长加法（39 位）。
但这听起来操作很多。您可以通过将多个 BCD 数字打包成一个整数来 "parallelize" 它们：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 位数字（7 轮 39 位），以及 64 位运算，12 位（4 轮 39 位）。
如果您只想将数字编码为字符串
使用 hex 数字，因为您可以通过位操作转换所有数字，所以速度很快...还使用 Base64 编码仅需位运算+翻译即可table。 Booth 表示只能在 O(n) 中的小型 int 算术上完成，其中 n 是打印数字的计数。
如果需要base10
然后打印一个 hex 字符串并将其转换为十进制字符串，如下所示：
- str_hex2dec
这比 #1 慢得多，但在小型 int 算术上仍然可行......您也可以使用 [=14 反向执行此操作（从字符串输入数字） =] ...
对于 bigint 库，还有另一种方法可以简化 string/integer 转换：
BCD
二进制编码的十进制...打印为十六进制的数字是十进制数。所以每个数字有 4 位。这会浪费一些内存，但许多 CPU 支持 BCD 并且可以在本地对此类整数进行操作。
基础10^n
有时使用基础 10^n 而不是 2^m 而
10^n <= 2^m
m 是您的原子整数的位宽，n 是适合它的十进制数。
例如，如果您的原子无符号整数是 16 位，它最多可以容纳 65536 个基数 2 中的值。如果您使用基数 10000，您可以使用 zeropad 从左侧将每个原子打印为一个十进制数，然后简单地将所有这些打印件堆叠在一起。
这也会浪费一些内存，但通常不会太多（如果合理选择了位宽）并且您可以对整数使用标准指令。只有进位传播会有点变化...
例如对于 32 位字：
2^32 = 4294967296 >= 1000000000
所以我们每 32 位就浪费了 log2(4.2949...) = ~2.1 位。这比 BCD log2(16/10)*(32/4)= ~5.42 位要好得多，而且通常位宽更高时甚至更好
我找了一段时间想找到一种将整数转换为字符串的算法。我的要求是手动执行此操作，因为我使用的是我自己的大数字类型。我已经定义了 + - * /(with remainder)，但需要找到一种方法来从 double int 打印单个数字（高和低，如果 int 是 64 位，则总共 128 位）。
我看到了一些答案，例如
Convert integer to string without access to libraries
但想知道是否可以使用更快的算法。我愿意直接使用位（例如 base2 到 base10-string - 但是我找不到这样的算法），但我只是希望避免重复除以 10 对于可能大到 2^128 的数字。
您可以使用分而治之的方式使用您的标准库将部分转换为字符串（这通常在该工作中非常有效）。
因此，不必在每次迭代中都除以 10，例如，您可以除以 10**15，然后让您的库将块转换为 15 位数字的字符串。最多三步后，你就完成了。
当然，您必须对零填充进行一些字符串操作。但是也许你的图书馆也可以在这里帮助你，如果你对所有较低的部分使用类似 %015d 零填充格式，并且对于最高的非零部分使用非填充 %d格式。
你可以用一个人为的方法试试你的运气，如下。
可以使用二进制编码的十进制表示法来表示数字。在这种表示中，每个小数位存储在4位上，并且在执行加法时，如果两位数之和超过9，则加6并向左进位。
如果你预先存储了2的所有次方的BCD表示，那么最多需要128次加法来进行转换。您可以节省一点，因为对于低幂，您不需要全长加法（39 位）。
但这听起来操作很多。您可以通过将多个 BCD 数字打包成一个整数来 "parallelize" 它们：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 位数字（7 轮 39 位），以及 64 位运算，12 位（4 轮 39 位）。
如果您只想将数字编码为字符串
使用 hex 数字，因为您可以通过位操作转换所有数字，所以速度很快...还使用 Base64 编码仅需位运算+翻译即可table。 Booth 表示只能在
O(n)中的小型 int 算术上完成，其中n是打印数字的计数。如果需要base10
然后打印一个 hex 字符串并将其转换为十进制字符串，如下所示：
- str_hex2dec
这比 #1 慢得多，但在小型 int 算术上仍然可行......您也可以使用 [=14 反向执行此操作（从字符串输入数字） =] ...
对于 bigint 库，还有另一种方法可以简化 string/integer 转换：
BCD
二进制编码的十进制...打印为十六进制的数字是十进制数。所以每个数字有 4 位。这会浪费一些内存，但许多 CPU 支持 BCD 并且可以在本地对此类整数进行操作。
基础
10^n有时使用基础
10^n而不是2^m而10^n <= 2^mm是您的原子整数的位宽，n是适合它的十进制数。例如，如果您的原子无符号整数是 16 位，它最多可以容纳
65536个基数2中的值。如果您使用基数10000，您可以使用 zeropad 从左侧将每个原子打印为一个十进制数，然后简单地将所有这些打印件堆叠在一起。这也会浪费一些内存，但通常不会太多（如果合理选择了位宽）并且您可以对整数使用标准指令。只有进位传播会有点变化...
例如对于 32 位字：
2^32 = 4294967296 >= 1000000000所以我们每 32 位就浪费了
log2(4.2949...) = ~2.1位。这比 BCDlog2(16/10)*(32/4)= ~5.42位要好得多，而且通常位宽更高时甚至更好