c++ - 将大的十六进制数转换为十进制形式(基数为 10 的形式)的算法

Question

我有一个字节数组和该数组的长度。目标是输出包含以 10 进制表示的数字的字符串。

我的数组是小端。这意味着第一个 (arr[0]) 字节是最低有效字节。这是一个例子:

#include <iostream>
using namespace std;

typedef unsigned char Byte;

int main(){
  int len = 5;
  Byte *arr = new Byte[5];
  int i = 0;

  arr[i++] = 0x12;
  arr[i++] = 0x34;
  arr[i++] = 0x56;
  arr[i++] = 0x78;
  arr[i++] = 0x9A;

  cout << hexToDec(arr, len) << endl;
}

数组由[0x12, 0x34, 0x56, 0x78, 0x9A]组成。我要实现的函数 hexToDec 应该返回 663443878930，这是十进制数。

但是，问题是因为我的机器是32位所以它输出2018915346(注意这个数字是从整数溢出获得的>).所以，问题是因为我使用的是天真的方式(迭代数组并将其乘以 256 到数组中位置的幂，然后乘以该位置的字节，最后添加到和)。这当然会产生整数溢出。

我也尝试过使用 long long int，但在某些时候，当然会发生整数溢出。

我想表示为十进制数的数组可能很长(超过 1000 字节)，这肯定需要比我天真的算法更聪明的算法。

问题

实现该目标的好算法是什么？另外，我必须问的另一个问题是该算法的最佳复杂度是多少？能否以线性复杂度 O(n) 完成，其中 n 是数组的长度？我实在想不出什么好主意。实现不是问题，问题是我缺乏想法。

建议或想法如何做到这一点就足够了。但是，如果使用一些代码更容易解​​释，请随意使用 C++ 编写。

Answer 1

您可以在 O(n) 中实现也可以不实现。一切都取决于您的号码的内部表示。

1. 对于真正的二进制形式(2 的幂，如 256)

   这在 O(n) 中是不可解的吗？这种数字的十六进制打印在 O(n) 中，但是您可以将 HEX 字符串转换为 decadic 并像这样转换回来:

   • How to convert a gi-normous integer (in string format) to hex format?

   因为创建十六进制字符串不需要 bignum 数学。因此，您只需在 HEX 中打印从 MSW 到 LSW 的数组。这是 O(n) 但转换为 DEC 不是。

   要在 decadic 中打印 bigint，您需要连续将其取模/除以 10，获得从 LSD 到 MSD 的数字，直到子结果为零。然后以相反的顺序打印它们......除法和模数可以立即完成，因为它们是相同的操作。因此，如果您的号码有 N 十进制数字，那么您需要 N bigint 划分。例如，每个 bigint 除法都可以通过二进制除法来完成，所以我们需要 log2(n) 位移和减法，它们都是 O(n)，所以 native bigint 打印的复杂度是:

   O(N.n.log2(n))
   

   我们可以通过对数从 N 计算 n，因此对于 BYTE s:

   N = log10(base^n)
     = log10(2^(8.n))
     = log2(2^(8.n))/log2(10)
     = 8.n/log2(10)
     = 8.n*0.30102999
     = 2.40824.n
   

   所以复杂度将是:

   O(2.40824.n.n.log2(n)) = O(n^2.log2(n))
   

   这对于非常大的数字来说是疯狂的。

2. 10 进制二进制形式的幂

   要在 O(n) 中执行此操作，您需要稍微更改数字的基数。它仍将以二进制形式表示，但基数将是 10 的幂。

   例如，如果您的数字将由 16bit WORDs 表示，您可以使用仍然适合它的最高基数 10000(最大为 16536 )。现在，您可以轻松地以 decadic 打印，只需打印数组中的每个单词，从 MSW 到 LSW。

   例子:

   让大量的 1234567890 存储为 BYTEs 和基础 100，其中 MSW 在前。所以号码会这样存储

   BYTE x[] = { 12, 34, 56, 78, 90 }
   

   但是正如您在使用 BYTEs 和基本 100 时看到的那样，我们在浪费空间，因为在整个 100*100/256=~39% 范围内只使用了 BYTE。对此类数字的操作与原始二进制形式略有不同，因为我们需要以不同方式处理上溢/下溢和进位标志。

3. BCD(二进制编码的十进制)

   还有另一种选择是使用BCD(二进制编码的十进制)，它与前面的选项几乎相同，但基数 10 用于数字的单个数字...每个 nibel ( 4 位)正好包含一个数字。处理器通常具有用于此数字表示的指令集。用法类似于二进制编码的数字，但在每个算术运算之后是称为 DAA 的 BCD 恢复指令，它使用进位和辅助进位标志状态来恢复结果的 BCD 编码。要以十进制打印 BCD 中的值，您只需将值打印为 HEX。前面示例中的数字将像这样用 BCD 编码:

   BYTE x[] = { 0x12, 0x34, 0x56, 0x78, 0x90 }
   

当然 #2,#3 将无法在 O(n) 中打印您的号码的 HEX。