快速计算 __m128i 寄存器中设置位数的方法

Question

快速计算 __m128i 寄存器中设置位数的方法

cssesimdsse2hammingweight

12

我应该计算一个__m128i寄存器内设置为1的位数。

特别地，我应编写两个函数，能够使用以下方式计数寄存器中的位数：

寄存器中设置为1的位的总数。
每个字节中设置为1的位的数量。

是否有内置函数可以完全或部分地执行上述操作？

- enzom83

3

最近的CPU有一条“POPCNT”（population count）指令；GCC通过内置的“__builtin_popcount”将其公开。 - Kerrek SB

2

请访问http://graphics.stanford.edu/~seander/bithacks.html以获取更多相关信息。 - Jim Balter

1

微软也有popcount函数...请参见https://dev59.com/jmgu5IYBdhLWcg3wv5Ya ...请注意，这些函数不一定比bithacks更快；如果在数组中计算位数，则一些bithack函数会稍微快一些。 - Jim Balter

4个回答

2

这是一个基于Bit Twiddling Hacks - Counting Set Bits in Parallel版本的，命名类似于其他内置函数的版本，并且还包括一些额外的16、32和64位向量函数。

#include "immintrin.h"

/* bit masks: 0x55 = 01010101, 0x33 = 00110011, 0x0f = 00001111 */
static const __m128i m1 = {0x5555555555555555ULL,0x5555555555555555ULL};
static const __m128i m2 = {0x3333333333333333ULL,0x3333333333333333ULL};
static const __m128i m3 = {0x0f0f0f0f0f0f0f0fULL,0x0f0f0f0f0f0f0f0fULL};
static const __m128i m4 = {0x001f001f001f001fULL,0x001f001f001f001fULL};
static const __m128i m5 = {0x0000003f0000003fULL,0x0000003f0000003fULL};

__m128i _mm_popcnt_epi8(__m128i x) {
    /* Note: if we returned x here it would be like _mm_popcnt_epi1(x) */ 
    __m128i y;
    /* add even and odd bits*/
    y = _mm_srli_epi64(x,1);  //put even bits in odd place
    y = _mm_and_si128(y,m1);  //mask out the even bits (0x55)
    x = _mm_subs_epu8(x,y);   //shortcut to mask even bits and add
    /* if we just returned x here it would be like _mm_popcnt_epi2(x) */ 
    /* now add the half nibbles */
    y = _mm_srli_epi64 (x,2); //move half nibbles in place to add
    y = _mm_and_si128(y,m2);  //mask off the extra half nibbles (0x0f)
    x = _mm_and_si128(x,m2);  //ditto
    x = _mm_adds_epu8(x,y);   //totals are a maximum of 5 bits (0x1f)
    /* if we just returned x here it would be like _mm_popcnt_epi4(x) */ 
    /* now add the nibbles */
    y = _mm_srli_epi64(x,4);  //move nibbles in place to add
    x = _mm_adds_epu8(x,y);   //totals are a maximum of 6 bits (0x3f)
    x = _mm_and_si128(x,m3);  //mask off the extra bits
    return x;
}

__m128i _mm_popcnt_epi16(__m128i x) {
    __m128i y;
    x = _mm_popcnt_epi8(x);    //get byte popcount
    y = _mm_srli_si128(x,1);   //copy even bytes for adding
    x = _mm_add_epi16(x,y);    //add even bytes into the odd bytes
    return _mm_and_si128(x,m4);//mask off the even byte and return
}

__m128i _mm_popcnt_epi32(__m128i x) {
    __m128i y;
    x = _mm_popcnt_epi16(x);   //get word popcount
    y = _mm_srli_si128(x,2);   //copy even words for adding
    x = _mm_add_epi32(x,y);    //add even words into odd words
    return _mm_and_si128(x,m5);//mask off the even words and return
}

__m128i _mm_popcnt_epi64(__m128i x){
    /* _mm_sad_epu8() is weird
       It takes the absolute difference of bytes between 2 __m128i
       then horizontal adds the lower and upper 8 differences
       and stores the sums in the lower and upper 64 bits
    */
    return _mm_sad_epu8(_mm_popcnt_epi8(x),(__m128i){0});
}

int _mm_popcnt_si128(__m128i x){
    x = _mm_popcnt_epi64(x);
    __m128i y = _mm_srli_si128(x,8);
    return _mm_add_epi64(x,y)[0];
    //alternative: __builtin_popcntll(x[0])+__builtin_popcntll(x[1]);
}

- technosaurus

为什么在第一步之后的步骤中需要饱和加法（saturating adds）而不是常规加法（add）？（尽管根据Agner Fog的指令表，paddusb在所有方面的性能与paddb相同，因此没有性能原因来避免使用饱和加法。这只是令人惊讶。） - Peter Cordes

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位的问题，但对我来到这里时提出的问题给出了一个不错的答案 :)

- yota

-3

编辑：我想我没有理解 OP 寻找什么，但我会保留我的答案，以防其他人偶然发现它有用。

C 语言提供了一些不错的位运算操作。

以下是计算整数中设置的位数的代码：

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

解释：

toCount % 2

返回我们整数中的最后一位（通过除以二并检查余数）。我们将此添加到我们的总计中，然后将我们的 toCount 值的位移一位。应该继续执行此操作，直到 toCount 中没有设置更多位（当 toCount 等于 0 时）

要计算特定字节中的位数，您将需要使用掩码。以下是一个示例：

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

假设在我们的系统中，我们认为字节0是小端系统中最不重要的字节。我们想要创建一个新的toCount，通过屏蔽设置为0的位来传递给我们之前的countBitsSet函数。我们通过将一个充满1的字节（用字母F表示）向我们想要的位置（每个字节8位）移位，并对我们的toCount变量执行按位与操作来实现这一点。

- Perfect Tommy

3

有内置函数（映射到CPU指令的内部函数，如POPCNT），问题是关于在128位SSE（XMM）寄存器中计算设置位数，而不是一个int。 - Paul R

啊，我明白了，我没有完全理解这个问题。如果合适的话，我会编辑我的回答，并保持它的存在，以防有人偶然发现它会有所帮助。 - Perfect Tommy

1

C语言没有提供“好用”的位运算。你甚至不能可移植地得到算术右移！实现允许是二进制补码，但对于有符号类型的>>却是逻辑移位。但在实践中，人们真正想使用的所有编译器都会为有符号类型提供算术右移，因此如果toCount为负数，则您的函数将成为一个无限循环。而有符号的％2比&1需要更多的工作，因为它必须为负奇数产生-1。但是（在正常的编译器上），如果toCount为负数，则您的函数永远不会返回，因此该问题被隐藏了... - Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marat Dukhan · Accepted Answer

以下是我在一个旧项目中使用的一些代码（有一篇研究论文与之相关）。下面的popcnt8函数计算每个字节中设置的位数。

仅基于SSE2的版本（基于Hacker's Delight book中的算法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，但使用的是XOP指令，在AMD Bulldozer上更快）

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 位和高 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
}