将大十六进制数转换为十进制形式的算法(基数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基的幂为2 5 6) 这在O(n)中是不可解决的，但是，这样数字的十六进制打印在O(n)中，您可以将 hex 字符串转换为十进或十进返回，如下所示：

- [How to convert a gi-normous integer (in string format) to hex format?](https://stackoverflow.com/a/18231860/2521214)

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

要在十进制中打印bigint，您需要通过10条连续的mod/div来获得从LSD到MSD的数字，直到子结果为零。然后按反序打印..。由于它们是相同的运算，所以可以同时进行除法和模运算。因此，如果您的数字有N十进数字，那么您需要N双除法。每个bigint除法都可以通过二进制除法来完成，因此我们需要log2(n)位移位和减法，这些都是O(n)，因此原生bigint打印的复杂性是：

O(N.n.log2(n))

我们可以通过对数从N计算n，因此对于BYTEs：

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

因此，复杂性将是：

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

这是一个非常大的数字。

1. 10基二元形式的幂 要在O(n)中做到这一点，您需要稍微更改数字的基数。它仍将以二进制形式表示，但基数为10的幂。 例如，如果您的数字将由16bit WORDs表示，则可以使用仍然适合它的最高基10000 (max为16536)。现在，您可以方便地在十进制中打印，因此，从、MSW、到LSW，数组中的每个单词都可以打印出来。 示例： 让我们以BYTEs的形式存储大量的BYTEs，其中MSW排在第一位。因此，该数字将按以下方式存储 字节x[] ={ 12，34，56，78，90 } 但是，正如您所看到的，在使用BYTEs和基本100时，我们正在浪费空间，因为只有100*100/256=~39%是从完整的BYTE范围使用的。这些数字上的操作与原始二进制格式略有不同，因为我们需要处理溢出/下溢，并以不同的方式携带标志。
2. BCD (二进制编码十进制) 还有一个选项是使用BCD (二进制编码十进制)，它与以前的选项几乎相同，但基数10用于数字的单数.每一个nibel (4位)都包含一个数字。处理器通常有用于此数字表示的指令集。其用法类似于二进制编码数字，但每次算术运算后，、BCD、恢复指令称为DAA，它使用进位和辅助进位标志状态恢复BCD编码的结果。要在BCD中以十进格式打印值，只需将值打印为HEX。前面示例中的数字将用BCD编码如下： 字节x[] ={ 0x12，0x34，0x56，0x78，0x90 }

当然，两个#2，#3将使HEX打印您的号码在O(n)上是不可能的。

Answer 2

您发布的0x9a78563412号，正如您用小endian格式表示的那样，可以用以下代码转换为适当的uint64_t：

#include <iostream>
#include <stdint.h>

int main()
{
    uint64_t my_number = 0;
    const int base = 0x100; /* base 256 */
    uint8_t array[] = { 0x12, 0x34, 0x56, 0x78, 0x9a };

    /* go from right to left, as it is little endian */
    for (int i = sizeof array; i > 0;) {
        my_number *= base;
        my_number += array[--i];
    }
    std::cout << my_number << std::endl; /* conversion uses 10 base by default */
}

样本运行结果如下：

$ num
663443878930

由于我们所处的基数正好是2的幂，所以我们可以使用

my_number <<= 8; /* left shift by 8 */
my_number |= array[--i]; /* bit or */

由于这些运算比整数乘法和求和更简单，因此在这样做时，预期会提高一些(但不是很大)的效率。与第一个示例一样，保留它应该更有表现力，因为它更多地代表一个任意的基转换。

Answer 3

你需要提高你的小学技能并实施长除法。

我认为最好在基数16中实现长除法(每次迭代除以0x0A )。请记住每一个除法--这些是您的小数位数(第一个是最不重要的数字)。