6

我正在尝试通过以下方式将二进制数组转换为十进制：

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 位二进制数组转换为十进制，并且我必须这样做一百万次。

任何人都可以帮助我，有没有更快的方法来完成上述操作？还是上面那个好看？

4

5 回答 5

5

你的方法是足够的，称之为好我不会混合按位运算和转换为十进制的“数学”方式，即使用

    decimal = decimal << 1 | array[i];

或者

    decimal = decimal * 2 + array[i];
于 2013-02-06T08:39:08.197 回答
2

在尝试任何优化之前，分析代码很重要。计时，查看正在生成的代码，并仅在您了解正在发生的事情时进行优化。

正如已经指出的那样，最好的优化不是做某事，而是进行更高级别的更改以消除需求。

然而...

您可能希望在此处轻松进行的大多数更改可能是编译器已经完成的事情（移位与编译器的乘法相同）。有些实际上可能会阻止编译器进行优化（将 an 更改add为 anor将限制编译器 - 还有更多添加数字的方法，只有您知道在这种情况下结果将是相同的）。

指针算法可能更好，但编译器并不愚蠢——它应该已经生成了用于取消引用数组的体面的代码，所以你需要检查你实际上没有通过引入一个额外的变量来使事情变得更糟。

在这种情况下，循环计数是明确定义和限制的，因此展开可能是有意义的。

此外，这取决于您希望结果对目标架构的依赖程度。如果您想要可移植性，则很难（呃）进行优化。

例如，下面的代码在这里产生了更好的代码：

unsigned int x0 = *(unsigned int *)array;
unsigned int x1 = *(unsigned int *)(array+4);

int decimal = ((x0 * 0x8040201) >> 20) + ((x1 * 0x8040201) >> 24);

我可能还可以推出一次 8 位而不是 4 位的 64 位版本。

但它绝对不是可移植的代码。如果我知道自己在运行什么并且只想快速处理数字，我可能会在本地使用它。但我可能不会把它放在生产代码中。当然不是没有记录它做了什么，也没有附带的单元测试来检查它是否真的有效。

于 2013-02-06T09:51:17.630 回答
0

您可以使用accumulate, 加倍并添加二进制操作：

int doubleSumAndAdd(const int& sum, const int& next) {
    return (sum * 2) + next;
}

int decimal = accumulate(array, array+ARRAY_SIZE,
                         doubleSumAndAdd);

这产生大端整数，而 OP 代码产生小端。

于 2013-02-06T09:51:52.443 回答
0

二进制“压缩”可以概括为加权和问题——为此有一些有趣的技术。

  • 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 *)数组；返回 (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 内在函数。

于 2013-02-06T11:43:52.727 回答
0

试试这个，我转换了一个最多 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;
}

从理论上讲，这种方法适用于无限长度的二进制数字

于 2015-03-15T11:10:38.283 回答