6 c++ memory arrays algorithm hex
我有一个字节数组和该数组的长度.目标是输出包含表示为基数为10的数字的字符串.
我的阵列是小端.这意味着first(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个字节),definitelly需要比我天真的更聪明的算法.
题
实现这一目标的好算法是什么？另外,我必须问的另一个问题是该算法的最佳复杂性是什么？它可以在线性复杂度O(n)中完成,其中n数组的长度是多少？我真的想不出一个好主意.实施不是问题,我缺乏想法.
建议或想法如何做到这一点就足够了.但是,如果使用某些代码更容易解释,请随意使用C++编写.
你可以也不能在 中实现这一点O(n)。一切都取决于您号码的内部表示。
对于真正的二进制形式（2 基数的幂，如 256）
O(n)然而，这个数字的十六进制打印在中是不可解决的O(n)，您可以将十六进制字符串转换为十进制并返回，如下所示：
因为创建十六进制字符串不需要 bignum 数学。您只需以HEX 格式打印从MSW到LSW 的数组即可。这是，但转换为DEC却不是。O(n)
要以十进制打印 bigint，您需要连续对其进行 mod/div 10 获取从LSD到MSD 的数字，直到子结果为零。然后以相反的顺序打印它们......除法和模数可以一次完成，因为它们是相同的运算。因此，如果您的数字有N十进制数字，那么您需要Nbigint 除法。每个 bigint 除法都可以通过二进制除法来完成，因此我们需要log2(n)位移位和减法，O(n)因此本机打印的复杂性bigint是：
O(N.n.log2(n))
N我们可以通过n对数来计算BYTEs：
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))
这对于非常大的数字来说是疯狂的。
10 基二进制形式的幂
为此，O(n)您需要稍微更改数字的基数。它仍以二进制形式表示，但基数为 10 的幂。
例如，如果您的数字将由 表示，16bit WORDs您可以使用10000仍然适合的最高基数（最大值为16536）。现在，您可以轻松地以十进制打印，只需依次打印数组中从MSW到LSW的每个单词即可。
例子：
让我们1234567890存储大数字，就像MSWBYTEs首先出现的基数100一样。所以号码将被存储如下
BYTE x[] = { 12, 34, 56, 78, 90 }
但正如您在使用BYTEs和底座时所看到的100，我们浪费了空间，因为仅100*100/256=~39%在整个BYTE范围内使用。对这些数字的操作与原始二进制形式略有不同，因为我们需要以不同的方式处理上溢/下溢和进位标志。
BCD（二进制编码的十进制）
还有另一种选择是使用BCD（二进制编码的十进制），它与之前的选项几乎相同，但基数 10 用于数字的单个数字...每个 nibel（4 位）仅包含一个数字。处理器通常具有用于此数字表示的指令集。其用法类似于二进制编码数，但在每次算术运算之后都是BCD恢复指令，称为类似DAA，它使用进位和辅助进位标志状态来恢复结果的BCD编码。要以十进制打印BCD值，只需将该值打印为HEX即可。前面示例中的数字将以 BCD 编码，如下所示：
BYTE x[] = { 0x12, 0x34, 0x56, 0x78, 0x90 }
当然，#2、#3都会使您的号码的十六进制打印变得不可能O(n)。