在不使用固定长度变量存储结果的情况下将十六进制数转换为十进制形式的最快算法

Fastest algorithm to convert hexadecimal numbers into decimal form without using a fixed length variable to store the result

我想编写一个程序将十六进制数转换为十进制形式,而不使用固定长度的变量来存储结果,因为这会限制我的程序可以使用的输入范围。

假设我要使用 long long int 类型的变量来计算、存储和打印结果。这样做会将我的程序可以处理的十六进制数范围限制在 80000000000000017FFFFFFFFFFFFFFF 之间。超出此范围的任何内容都会导致变量溢出。

我确实编写了一个程序,通过执行进位和借位操作来计算小数结果并将其存储在动态分配的字符串中,但它运行起来要慢得多,即使对于 7FFFFFFFF 这样大的数字也是如此!

然后我偶然发现了 this site,它可以接受超出 64 位变量范围的数字。我用比 16^65 - 1 大得多的数字尝试了他们的转换器,但仍然无法使其溢出。它只是继续前进并打印结果。

我认为他们必须使用一种更好的十六进制到十进制转换算法,该算法不限于 64 位值。

到目前为止,Google 的搜索结果只让我想到了使用一些固定长度变量来存储结果的算法。

这就是我来这里的原因。我想知道这样的算法是否存在,如果存在,它是什么?

嗯,听起来你在写 "a program that calculates and stores the decimal result in a dynamically allocated string by performing carry and borrow operations" 的时候已经做到了。

从 16 进制(十六进制)转换为 10 进制意味着在 10x 表示中实现数字的乘法和加法。然后对于每个十六进制数字 d,您计算 result = result*16 + d。完成后,您将获得基于 10 的表示形式中的相同数字,该表示形式很容易写成十进制字符串。

您的基于字符串的方法运行缓慢的原因可能有多种。如果您提供,我相信有人会发表评论。

不过,要使它相当快,最重要的技巧是选择正确的碱基进行转换。我可能会以 109 为基数进行乘法和加法运算,这样每个数字都将尽可能大,同时仍适合 32 位整数,并以 7 个十六进制数字处理时间,这是我能做到的,但只乘以个位数。

对于每 7 个十六进制数字,我会将它们转换为数字 d,然后执行 result = result * ‭(16^7) + d.

然后我可以获得以 109.

为基数的每个结果数字的 9 个十进制数字

这个过程非常简单,因为您只需乘以个位数。我确信有更快、更复杂的方法可以递归地将数字分成大小相等的部分。