以最佳方式将十进制转换为二进制

Question

将十进制数转换为二进制形式的最佳方法是什么，即具有最佳时间复杂度？

通常将十进制数转换为二进制数，我们不断地将数除以 2 并存储其余数。但是如果十进制数非常大，这将花费很长时间。这种情况下的时间复杂度为O(log n)。

所以我想知道除此之外是否还有其他方法可以以更好的时间复杂性完成我的工作？

Answer 1

问题本质上是使用二进制整数算术计算多项式，因此结果是二进制的。认为

\n

p(x) = a\xe2\x82\x80x\xe2\x81\xbf + a\xe2\x82\x81x\xe2\x81\xbf\xe2\x81\xbb\xc2\xb9 + \xe2\x8b\xaf + a\xe2\x82\x99\xe2\x82\x8b\xe2\x82\x81x + a\xe2\x82\x99\n

\n

现在，如果a\xe2\x82\x80,a\xe2\x82\x81,a\xe2\x82\x82,\xe2\x8b\xaf,a\xe2\x82\x99是该数字的十进制数字（每个数字隐式地用 0 到 9 范围内的二进制数表示），并且我们在 x=10 处计算 p（隐式地以二进制表示），那么结果就是十进制数字序列表示的二进制数。

\n

在给定系数作为输入的情况下，在单点评估多项式的​​最佳方法是霍纳法则。这相当于以一种易于评估的方式重写 p(x)，如下所示。

\n

p(x) = ((\xe2\x8b\xaf((a\xe2\x82\x80x + a\xe2\x82\x81)x + a\xe2\x82\x82)x + \xe2\x8b\xaf )x + a\xe2\x82\x99\xe2\x82\x8b\xe2\x82\x81)x + a\xe2\x82\x99\n

\n

这给出了以下算法。这里数组 a[] 包含十进制数的数字，从左到右，每个数字表示为 0 到 9 范围内的小整数。从 0 索引的数组的伪代码：

\n

    toNumber(a[])\n        const x = 10\n        total = a[0]\n        for i = 1 to a.length - 1 do\n            total *= x    //multiply the total by x=10\n            total += a[i]  //add on the next digit\n        return total\n

\n

在数字以二进制表示的机器上运行此代码会得到二进制结果。因为这就是我们在这个星球上所拥有的，这给了你你想要的。

\n

如果您想获取实际的位，现在您可以使用高效的二进制运算从您构建的二进制数中获取它们，例如掩码和移位。

\n

其复杂性与位数成线性关系，因为机器整数上的算术运算是常数时间，并且每个数字执行两次操作（除了第一个操作）。这是一个很小的工作量，所以速度非常快。

\n

如果您需要非常大的数字，大于 64 位，只需使用某种大整数。如果实施得当，这将降低算术成本。

\n

如果您的大整数实现需要，为了避免尽可能多的大整数算术，请将数字数组分成 19 位数字的切片，最左边的切片可能更少。19 是可以转换为（无符号）64 位整数的最大位数。

\n

将每个块如上所述转换为二进制，而不使用大整数，并按从左到右的顺序创建这些 64 位值的新数组。现在，这些是要在 x=10\xc2\xb9\xe2\x81\xb9 处计算的多项式的系数。与上述相同的算法只能用于大整数算术运算，其中 10 替换为 10\xc2\xb9\xe2\x81\xb9，在使用之前应使用大整数算术对其进行评估。

\n