6

次の方法でバイナリ配列を10進数に変換しようとしています:

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 ビットのバイナリ配列を 10 進数に変換する必要があり、それを何百万回も行う必要があります。

上記を行うためのより速い方法はありますか？それとも、上記のものはいいですか？

4

5 に答える 5

5

あなたの方法は適切です。それを素晴らしいと呼ぶには、ビット単位の操作と10進数に変換する「数学的な」方法を混在させません。つまり、どちらかを使用します

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

また

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

最適化を試みる前に、コードのプロファイルを作成することが重要です。時間を計り、生成されているコードを見て、何が起こっているのかを理解したときにのみ最適化します。

そして、すでに指摘したように、最善の最適化は、何かをするのではなく、必要性を排除するより高いレベルの変更を行うことです。

でも...

ここで簡単に行うことができるほとんどの変更は、コンパイラーがすでに行ったことである可能性があります（シフトはコンパイラーへの乗算と同じです）。コンパイラが最適化を行うのを実際に妨げるaddものもあります（をに変更するとorコンパイラが制限されます。数値を追加する方法は他にもありますが、この場合は結果が同じになることを知っているのはあなただけです）。

ポインター演算の方が優れているかもしれませんが、コンパイラーは愚かではありません。配列を逆参照するための適切なコードを既に生成しているはずなので、追加の変数を導入して実際に問題が悪化していないことを確認する必要があります。

この場合、ループカウントは明確に定義され、制限されているため、展開することはおそらく理にかなっています。

さらに、結果をターゲットアーキテクチャにどの程度依存させるかによって異なります。移植性が必要な場合、最適化するのは困難です。

たとえば、次のコードはここでより良いコードを生成します。

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

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

おそらく、一度に4ビットではなく8ビットを実行する64ビットバージョンをロールすることもできます。

しかし、それは間違いなく移植可能なコードではありません。自分が何を実行しているのかを知っていて、数値をすばやく処理したい場合は、ローカルで使用する可能性があります。しかし、私はおそらくそれを本番コードに入れないでしょう。確かに、それが何をしたかを文書化することなく、そしてそれが実際に機能することをチェックする付随する単体テストなしではありません。

于 2013-02-06T09:51:17.630 に答える
0

accumulate二項演算を2倍および加算して、を使用できます。

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 などであるため、各桁を 2 倍の重みで合計することを意味します。

    エンコードがビッグ エンディアンの場合、*(unsigned long long)array % 254 は加重合計を生成します (切り捨てられた範囲は 0..253)。次に、重み 2 の値を削除して手動で追加すると、正しい結果が得られます。

    uint64_t a = *(uint64_t *)array; return (a & ~256) % 254 + ((a>>9) & 2);

重みを取得する他のメカニズムは、各 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;

もう 1 つの興味深い手法は、crc32 を圧縮関数として利用することです。結果が LookUpTable[crc32(array) & 255]; となるだけです。256 の異なる配列のこの特定の小さなサブセットとの衝突がないためです。ただし、それを適用するには、移植性の低い道をすでに選択しており、SSE 組み込み関数を使用することになる可能性があります。

于 2013-02-06T11:43:52.727 に答える
0

これを試してみて、最大1020ビットの2進数を変換しました

#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;
}

理論的には、この方法は無限長の 2 進数に対して機能します。

于 2015-03-15T11:10:38.283 に答える