12

__m128i レジスタの設定ビット数をカウントする必要があります。特に、次の方法を使用して、レジスタのビット数をカウントできる 2 つの関数を作成する必要があります。

  1. レジスタの設定ビットの総数。
  2. レジスタの各バイトの設定ビット数。

上記の操作を全体的または部分的に実行できる組み込み関数はありますか?

4

4 に答える 4

28

ここに私が古いプロジェクトで使用したいくつかのコードがあります (それに関する研究論文があります)。以下の関数popcnt8は、各バイトに設定されたビット数を計算します。

SSE2 のみのバージョン ( Hacker's Delight book のAlgorithm 3 に基づく):

static const __m128i popcount_mask1 = _mm_set1_epi8(0x77);
static const __m128i popcount_mask2 = _mm_set1_epi8(0x0F);
static inline __m128i popcnt8(__m128i x) {
    __m128i n;
    // Count bits in each 4-bit field.
    n = _mm_srli_epi64(x, 1);
    n = _mm_and_si128(popcount_mask1, n);
    x = _mm_sub_epi8(x, n);
    n = _mm_srli_epi64(n, 1);
    n = _mm_and_si128(popcount_mask1, n);
    x = _mm_sub_epi8(x, n);
    n = _mm_srli_epi64(n, 1);
    n = _mm_and_si128(popcount_mask1, n);
    x = _mm_sub_epi8(x, n);
    x = _mm_add_epi8(x, _mm_srli_epi16(x, 4));
    x = _mm_and_si128(popcount_mask2, x);
    return x;
}

SSSE3 バージョン ( Wojciech Mulaによる):

static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
static inline __m128i popcnt8(__m128i n) {
    const __m128i pcnt0 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(n, popcount_mask));
    const __m128i pcnt1 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(_mm_srli_epi16(n, 4), popcount_mask));
    return _mm_add_epi8(pcnt0, pcnt1);
}

XOP バージョン (SSSE3 と同等ですが、AMD Bulldozer でより高速な XOP 命令を使用します)

static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
static const __m128i popcount_shift = _mm_set1_epi8(-4);
static inline __m128i popcount8(__m128i n) {
    const __m128i pcnt0 = _mm_perm_epi8(popcount_table, popcount_table, _mm_and_si128(n, popcount_mask));
    const __m128i pcnt1 = _mm_perm_epi8(popcount_table, popcount_table, _mm_shl_epi8(n, popcount_shift));
    return _mm_add_epi8(pcnt0, pcnt1);
}

以下の関数popcnt64は、SSE レジスタの下位および上位 64 ビット部分のビット数をカウントします。

SSE2 バージョン:

static inline __m128i popcnt64(__m128i n) {
    const __m128i cnt8 = popcnt8(n);
    return _mm_sad_epu8(cnt8, _mm_setzero_si128());
}

XOP バージョン:

static inline __m128i popcnt64(__m128i n) {
    const __m128i cnt8 = popcnt8(n);
    return _mm_haddq_epi8(cnt8);
}

最後に、popcnt128以下の関数は 128 ビット レジスタ全体のビット数をカウントします。

static inline int popcnt128(__m128i n) {
    const __m128i cnt64 = popcnt64(n);
    const __m128i cnt64_hi = _mm_unpackhi_epi64(cnt64, cnt64);
    const __m128i cnt128 = _mm_add_epi32(cnt64, cnt64_hi);
    return _mm_cvtsi128_si32(cnt128);
}

ただし、実装するより効率的な方法popcnt128は、ハードウェア POPCNT 命令を使用することです (それをサポートするプロセッサ上で):

static inline int popcnt128(__m128i n) {
    const __m128i n_hi = _mm_unpackhi_epi64(n, n);
    #ifdef _MSC_VER
        return __popcnt64(_mm_cvtsi128_si64(n)) + __popcnt64(_mm_cvtsi128_si64(n_hi));
    #else
        return __popcntq(_mm_cvtsi128_si64(n)) + __popcntq(_mm_cvtsi128_si64(n_hi));
    #endif
}
于 2013-06-28T00:21:48.187 に答える
0

最初のコメントで述べたように、gcc 3.4+ は (できれば最適な) ビルトイン経由で簡単にアクセスできます。

int __builtin_popcount (unsigned int x) /* Returns the number of 1-bits in x. */

ここに記載されているように： http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Other-Builtins.html#Other%20Builtins

128ビットの質問に正確に答えているわけではありませんが、ここに着いたときに持っていた質問に良い答えを与えてくれます:)

于 2014-04-29T15:19:14.803 に答える
-3

編集：OPが探していたものを理解していなかったと思いますが、これに出くわした他の誰かに役立つ場合に備えて、回答を維持しています。

C には、優れたビット演算がいくつか用意されています。

整数に設定されたビット数をカウントするコードは次のとおりです。

countBitsSet(int toCount)
{
    int numBitsSet = 0;
    while(toCount != 0)
    {
        count += toCount % 2;
        toCount = toCount >> 1;
    }
    return numBitsSet;
}

説明：

toCount % 2

整数の最後のビットを返します。(2 で割って余りを調べることにより)。これを合計カウントに追加し、toCount 値のビットを 1 だけシフトします。この操作は、toCount に設定されたビットがなくなるまで続行する必要があります (toCount が 0 の場合)。

特定のバイトのビット数をカウントするには、マスクを使用します。以下に例を示します。

countBitsInByte(int toCount, int byteNumber)
{
    int mask = 0x000F << byteNumber * 8
    return countBitsSet(toCount & mask)
}

私たちのシステムでは、バイト 0 をリトル エンディアン システムの最下位バイトと見なしているとしましょう。0 に設定されたビットをマスクすることによって、以前の countBitsSet 関数に渡す新しい toCount を作成します。これを行うには、1 でいっぱいのバイト (文字 F で示されます) を必要な位置 (byteNumber *バイト内の 8 ビットの場合は 8)、toCount 変数でビット単位の AND 演算を実行します。

于 2013-06-28T00:11:56.007 に答える