我正在尝试以以下方式将二进制数组转换为十进制：
uint8_t array[8] = {1,1,1,1,0,1,1,1} ;
int decimal = 0 ;
for(int i = 0 ; i < 8 ; i++)
decimal = (decimal << 1) + array[i] ;
实际上，我需要将64位二进制数组转换为十进制，并且需要做成百万次。
有人能帮我吗？是否有更快的方法来完成上述操作？或者上述方法已经很好了？
C++：二进制转十进制转换
5
- user1838343
4
3无论是位于数组中还是字符串中，都必须循环遍历比特位。可能有更多针对C++的特定方法，但最终总会有一个关于比特位的循环。 - Some programmer dude
这个问题可能会对你有所帮助：https://dev59.com/N0rSa4cB1Zd3GeqPUCt1 - Oren
5通常情况下，优化的效益不是从小函数中获得的，而是要从更高层次上思考。为什么数字要以这种方式存储？ - maxim1000
你可以使用循环展开和/或指针算术来代替数组访问。这样可以加快速度，但算法复杂度仍然相同。 - Jack Aidley
6个回答
4
您的方法足够好，如果称之为优秀，我只会建议不要混合位运算和“数学”方式将其转换为十进制，即只使用其中一种方式
decimal = decimal << 1 | array[i];
或者
decimal = decimal * 2 + array[i];
- unkulunkulu
1
1请注意，任何一个好的编译器都会将移位和乘法视为相同，而使用“或”代替加法将限制其优化能力。实际上，MSVC为此处的第一个示例生成较差的代码，但对于第二种情况与原始代码相同。 - JasonD
2
在尝试进行任何优化之前，对代码进行分析是非常重要的。计时，观察生成的代码，并且只有在理解正在发生的情况时才进行优化。
正如已经指出的那样，最好的优化方法是不做某些事情，而是进行更高级别的更改以消除需要。
然而...
你可能想要轻松地进行的大多数更改都可能是编译器已经完成的（对于编译器来说，移位与乘法是相同的）。有些实际上会阻止编译器进行优化（将一个add更改为or将限制编译器-有更多的方法来添加数字，而只有在这种情况下，你知道结果将是相同的）。
指针算术可能更好，但编译器并不愚蠢-它应该已经生成了适当的代码来取消引用数组，因此你需要检查是否实际上通过引入额外的变量而使事情更糟。
在这种情况下，循环计数是明确定义和有限的，因此展开循环可能是有意义的。
此外，这取决于你希望结果在多大程度上依赖于目标架构。如果你想要可移植性，进行优化会更加困难。
例如，下面的代码产生更好的代码：
unsigned int x0 = *(unsigned int *)array;
unsigned int x1 = *(unsigned int *)(array+4);
int decimal = ((x0 * 0x8040201) >> 20) + ((x1 * 0x8040201) >> 24);
我可以尝试制作一个64位版本，每次处理8位而不是4位。
但这肯定不是可移植的代码。如果我知道我运行的环境并且只想快速计算数字，我可能会在本地使用它。但我可能不会将其放入生产代码中。当然不能没有记录它所做的事情的文档，并且没有随附的单元测试来检查它是否实际工作。
- JasonD
2
此外，如果
array是一个实际的char array[8]，而不仅仅是指向匿名内存的char*，那么*(unsigned int *)array可能会导致严格别名未定义行为。并且，如果你没有使用alignas(unsigned) char array[8];，它可能会导致对齐未定义行为。使用memcpy(&tmp, array, sizeof(tmp))来进行严格别名安全的非对齐加载。这样可以使其完全可移植，至少在static_assert(sizeof(uint64_t) == 8)的系统上是如此。这不依赖于字节序或其他任何东西，尽管它依赖于8位字节。像uint64_t这样的类型保证没有填充。 - undefined0
二进制“压缩”可以广义地视为带权和问题，有一些有趣的技术可用。
- X mod（255）本质上意味着所有独立的8位数字求和。
X mod 254意味着将每个数字与加倍权重相加，因为1 mod 254 = 1，256 mod 254 = 2，256 * 256 mod 254 = 2 * 2 = 4等等。
如果编码是大端的，则*(unsigned long long)array % 254将产生一个加权和（截断范围为0..253）。 然后手动删除权重为2的值并添加它将产生正确的结果：
uint64_t a = *(uint64_t *)array; return (a & ~256) % 254 + ((a>>9) & 2);
获取权重的另一种机制是通过255预乘每个二进制数字并屏蔽正确的位数：
uint64_t a = (*(uint64_t *)array * 255) & 0x0102040810204080ULL; // little endian
uint64_t a = (*(uint64_t *)array * 255) & 0x8040201008040201ULL; // big endian
在这两种情况下，可以取255的余数（现在带权重1进行校正）：
return (a & 0x00ffffffffffffff) % 255 + (a>>56); // little endian, or
return (a & ~1) % 255 + (a&1);
对于怀疑的人来说：我实际上对模数版本进行了性能分析，发现在x64上比迭代稍微快一些。
继续JasonD的回答，可以通过迭代地使用并行位选择来解决问题。 但首先，将方程完整地表达出来有助于编译器消除迭代方法中累积所创建的人为依赖。
ret = ((a[0]<<7) | (a[1]<<6) | (a[2]<<5) | (a[3]<<4) |
(a[4]<<3) | (a[5]<<2) | (a[6]<<1) | (a[7]<<0));
对比。
HI=*(uint32_t)array, LO=*(uint32_t)&array[4];
LO |= (HI<<4); // The HI dword has a weight 16 relative to Lo bytes
LO |= (LO>>14); // High word has 4x weight compared to low word
LO |= (LO>>9); // high byte has 2x weight compared to lower byte
return LO & 255;
另一个有趣的技巧是利用crc32作为压缩函数；然后结果恰好是LookUpTable[crc32(array) & 255]；因为在这个给定的256个不同数组的小子集中没有冲突。但是，要应用它，就已经选择了更少可移植性的道路，最终可能会使用SSE内部函数。
- Aki Suihkonen
-1
你可以使用
accumulate 函数，结合加倍和加法的二进制操作：int doubleSumAndAdd(const int& sum, const int& next) {
return (sum * 2) + next;
}
int decimal = accumulate(array, array+ARRAY_SIZE,
doubleSumAndAdd);
这会产生大端整数，而OP代码会产生小端整数。
- Peter Wood
-2
试试这个，我把一个长达1020位的二进制数转换了
#include <sstream>
#include <string>
#include <math.h>
#include <iostream>
using namespace std;
long binary_decimal(string num) /* Function to convert binary to dec */
{
long dec = 0, n = 1, exp = 0;
string bin = num;
if(bin.length() > 1020){
cout << "Binary Digit too large" << endl;
}
else {
for(int i = bin.length() - 1; i > -1; i--)
{
n = pow(2,exp++);
if(bin.at(i) == '1')
dec += n;
}
}
return dec;
}
理论上，这种方法可以适用于无限长度的二进制数
- Braxton Nunnally
5
1你应该意识到
long 只有32（或64）位，无法容纳1020位的数据。 - Blastfurnace是的，你可能误读了。它的工作方式如下：二进制：101 十进制：5 我读取一个长达1020位的字符串，每次我遇到1时，我就加上2 * pow的值。 - Braxton Nunnally
尝试使用超过31或63位的字符串测试您的代码。您不可能用32或64位有符号整数表示1020位的值。结果会溢出并绕回。在ideone.com上查看您的代码运行。当我给它32位或更多时，结果是-1。显然
1020位无法用32位变量表示。 - Blastfurnace我正在设计一台虚拟机，它运行得非常好。我解码了一个1020位的二进制并将结果存储在double中。 - Braxton Nunnally
1这段代码没有使用或返回
double。即使您将其更改为使用 double，您也应该意识到 IEEE 754 双精度浮点数具有约 53 位（约 16 个十进制数字）的有效数字。您实际上无法在 double 中存储 1020 个有效位，它将是一个近似值。唯一可行的方法是使用一些大整数库。 - Blastfurnace-4
这是一种懒惰的方法，可以一次处理16位，而不使用指针算术、指数运算或位移/位掩码操作。方法是：在左侧放置15个嵌套的
所以，这个不考虑符号的64位完全展开版本看起来会像这样
2 * (，在右侧以大端顺序放置所有数组位。
function b2d_16_unsigned(_, __) {
# set __[_ = 1] for langs w/ 1-based indexing e.g. julia/lua/awk etc
return \
(_ += _ = split(_, __, _ = "")^_\
)*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_* \
__[_ = 0] \
+ __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_]
}
1110111110010101 61333
所以，这个不考虑符号的64位完全展开版本看起来会像这样
function b2d_64(_, signed_flag, __) { # signed_flag is 0/1
return \
(_ += _ = split(sprintf("%64s",_), __, _ = "")^_\
)*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(\
_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(\
_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(\
_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(_*(\
(+signed_flag ? -_ : _) * \
__[_ = 0] \
+ __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]) + __[++_]) + __[++_] \
) + __[++_]) + __[++_]) + __[++_]
}
1100010001100001010000100101000110000100110110001101110110110001 0
14150664422063398321
1100010001100001010000100101000110000100110110001101110110110001 1
-4296079651646153295
- RARE Kpop Manifesto
7
1这是什么语言？AWK？用C++版本会因为未定义的未排序
++而产生未定义的行为。而且，与uint64_t上的简单整数运算相比，sprintf远远不够快。 - undefined一个五千万位的十进制数无法容纳在一个
uint64_t中。我所说的是针对这个问题所需的整数运算，而不是你可以编造的任意例子。 - undefined@PeterCordes：在转换过程之前，你如何将一个64字节的ASCII二进制字符串放入一个单独的uint64_t中？ - undefined
你不需要这样做。你可以使用8字节的块来处理它，使用如何将8个布尔值转换为一个字节（反之亦然）？的方法，或者使用SSE2或AVX2 SIMD向量来处理16或32字节的块。或者你可以使用一个简单的
total = total*2 + digit来处理。无论如何，最终的结果是一个uint64_t，所以你所需要的最宽的累加器就是一个单独的uint64_t。 - undefined@PeterCordes ：所以你的解决方案是在一个即将消亡的架构上使用向量化指令？ - undefined
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接