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

coder 2024-02-06 原文

我有一个字节数组和该数组的长度。目标是输出包含以 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++ 编写。

最佳答案

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

对于真正的二进制形式(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))
```
这对于非常大的数字来说是疯狂的。
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。对此类数字的操作与原始二进制形式略有不同，因为我们需要以不同方式处理上溢/下溢和进位标志。
BCD(二进制编码的十进制)

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

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

关于c++ - 将大的十六进制数转换为十进制形式(基数为 10 的形式)的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45262037/

十进进制 code strong c++arrays algorithm memory hex

有关c++ - 将大的十六进制数转换为十进制形式(基数为 10 的形式)的算法的更多相关文章

ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby-on-rails - 使用回形针的嵌套形式 - 2
我有一个名为posts的模型，它有很多附件。附件模型使用回形针。我制作了一个用于创建附件的独立模型，效果很好，这是此处说明的View(https://github.com/thoughtbot/paperclip):@attachment,:html=>{:multipart=>true}do|form|%>posts中的嵌套表单如下所示:prohibitedthispostfrombeingsaved:@attachment,:html=>{:multipart=>true}do|at_form|%>附件记录已创建，但它是空的。文件未上传。同时，帖子已成功创建...有什么想法吗？
ruby - 我如何添加二进制数据来遏制 POST - 2
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
Ruby - 如何将消息长度表示为 2 个二进制字节 - 2
我正在使用Ruby，我正在与一个网络端点通信，该端点在发送消息本身之前需要格式化“header”。header中的第一个字段必须是消息长度，它被定义为网络字节顺序中的2二进制字节消息长度。比如我的消息长度是1024。如何将1024表示为二进制双字节？最佳答案 Ruby(以及Perl和Python等)中字节整理的标准工具是pack和unpack。ruby的packisinArray.您的长度应该是两个字节长，并且按网络字节顺序排列，这听起来像是n格式说明符的工作:n|Integer|16-bitunsigned,network(bi
ruby - 使用 `+=` 和 `send` 方法 - 2
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
ruby - 如何计算 Liquid 中的变量 +1 - 2
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。最佳答案因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
由于 libgmp.10.dylib 的问题，Ruby 2.2.0 无法运行 - 2
我刚刚安装了带有RVM的Ruby2.2.0，并尝试使用它得到了这个:$rvmuse2.2.0--defaultUsing/Users/brandon/.rvm/gems/ruby-2.2.0dyld:Librarynotloaded:/usr/local/lib/libgmp.10.dylibReferencedfrom:/Users/brandon/.rvm/rubies/ruby-2.2.0/bin/rubyReason:Incompatiblelibraryversion:rubyrequiresversion13.0.0orlater,butlibgmp.10.dylibpro
ruby - 如何在 Ruby 中将负整数转换为二进制 - 2
问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001
arrays - Ruby 数组 += vs 推送 - 2
我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“
Ruby#index 方法 VS 二进制搜索 - 2
给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？最佳答案内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

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

有关c++ - 将大的十六进制数转换为十进制形式(基数为 10 的形式)的算法的更多相关文章

随机推荐