Szybkie zliczanie ilości ustawionych bitów w rejestrze m128i

Oto baza wersji Bit Twidling hacków-liczenia ustawionych bitów równolegle z nazwami podobnymi do innych funkcji wewnętrznych, a także niektórych dodatkowych funkcji dla 16 wektorów 32 i 64 bitowych

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

Jak wspomniano w pierwszym komentarzu, gcc 3.4 + oferuje łatwy dostęp do (miejmy nadzieję optymalnego) wbudowanego za pośrednictwem

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

Jak podano tutaj: http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Other-Builtins.html#Other%20Builtins

Nie do końca odpowiada na pytanie za 128 bitów, ale daje mi ładną odpowiedź na pytanie, które miałem, gdy tu wylądowałem:)

Edit: chyba nie rozumiałem, czego szuka OP, ale podtrzymuję swoją odpowiedź na wypadek, gdyby była przydatna dla kogoś innego, kto się na to natknie.

C zapewnia kilka ładnych operacji bitowych.

Oto kod do zliczania liczby bitów ustawionych w liczbie całkowitej:

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

Wyjaśnienie:

toCount % 2

Zwraca ostatni bit w naszej liczbie całkowitej. (Dzieląc przez dwa i sprawdzając resztę). Dodajemy to do naszej liczby całkowitej, a następnie przesuwamy bity naszej wartości toCount przez jeden. Ta operacja powinna być kontynuowana, dopóki nie ma więcej bitów ustawionych w toCount (gdy toCount jest równe 0)

Aby zliczyć liczbę bitów w określonym bajcie, należy użyć maski. Oto przykład:

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

Powiedzmy, że w naszym systemie, uważamy bajt 0 za najmniej znaczący bajt w małym systemie endian. Chcemy utworzyć nowe toCount, aby przejść do naszej wcześniejszej funkcji countBitsSet, maskując bity, które są ustawione na 0. Robimy to przesuwając bajt pełna jedynek (oznaczonych literą F) do żądanej pozycji (numer bajtu * 8 dla 8 bitów w bajcie) i wykonująca bitową operację z naszą zmienną toCount.