1

私のプロジェクトでは、サイズ40バイト（320ビット）の2つのバイナリ配列をANDしてから、C++でセットビット数を計算する必要があります。これを行うためのアルゴリズムをいくつか見つけましたが、C++で実装する最速の方法を知りたいです。つまり、どのc ++データ型が適切でしょうか？（unsingedchar *、unsigned int 32、u_int64、...）。私の配列サイズは40バイトですが、多くのアルゴリズムが32ビット整数と互換性があることを知っています。

このリンクで説明されているアルゴリズムについてはどうですか： 高速ビットカウント技術どちらが高速ですか？

constタイプの方が良いですか、それとも違いはありませんか？

どんな助けでも大歓迎です。

4

3 に答える 3

6

つまり、どのc ++データ型が適切でしょうか？

std::bitset<320>。

思いついたアルゴリズムは、速度と利便性の点で次のアルゴリズムと比較する必要があります。

std::bitset<320> first;
std::bitset<320> other;

// twiddle bits here ...

std::bitset<320> and_result(first & other);
std::size_t number_of_bits(and_result.count());

選択肢がそれほど速くならない場合は、上記のようなコードを使用してください。それはあなたの意図を明確に表現し、後のメンテナンスの頭痛の種を避けます。

于 2012-09-27T22:07:19.183 に答える
6

これは、一度に4バイトの配列を通過し、10回の反復が必要なバージョンです。

uint32_t *arr1_int = (uint32_t*) arr1;
uint32_t *arr2_int = (uint32_t*) arr2;
int i;
int bits_set = 0;

for (i = 0; i < 10; i++) {
    uint32_t v = arr1_int[i] & arr2_int[i];

    /* http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel */
    v = v - ((v >> 1) & 0x55555555);                   
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);    
    bits_set += ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

コンパイラ組み込み関数を使用すると、最新のCPUでこれをはるかに高速に実行できます。たとえば、Visual C ++を搭載した64ビットCPUの場合：

#include <intrin.h>

__int64 *arr1_int = (__int64*) arr1;
__int64 *arr2_int = (__int64*) arr2;
int bits_set = 0;

/* 40 / 8 bytes == 5 iterations */
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);

しかし、これはすべてパフォーマンスを念頭に置いたものです。Robが提案したものと確実に一致する読み取り可能なコードが必要な場合は、

于 2012-09-27T22:07:23.033 に答える
2

このような単純なものは、十分に高速である必要があります。

const uint8_t LUT[256] = { 0, 1, 1, 2, ..., 8 }; // pop count LUT for bytes

int count_bits(const uint8_t *a1, const uint8_t *a2, int n)
{
    int count = 0;

    for (int i = 0; i < n; ++i)
    {
        count += LUT[a1[i] & a2[i]];
    }
    return count;
}

バイトごとに3つのロードと2つのALU操作があります。つまり、40バイトのユースケースでは120のロードと80のALU操作です。

それを試して、プロファイルを作成してください。十分に高速でない場合は、より高速な可能性のあるより複雑なソリューションを検討できます。

于 2012-09-27T22:08:03.910 に答える