はわわーっ

はわわわわっ

popcntのメモ

なんかおもしろそうなもの見つけたので。
ビットを数える・探すアルゴリズム

なんでこれで動くんだろうな…
ぜんぜんわからん………

#include <stdio.h>
#include <stdint.h>


uint16_t bs16[] = { 0x3548, 0x4aa2, 0x6f68, 0x2116,
                    0x7e1d, 0x5ac3, 0x3a23, 0x60c8,
                    0x6e8d, 0x1706, 0x7d0d, 0x5879 };

uint32_t bs32[] = { 0x3548579c, 0x4aa22392, 0x6f685609, 0x21161a48,
                    0x7e1d47bf, 0x5ac3760a, 0x3a231b73, 0x60c8595f,
                    0x6e8d1033, 0x1706604e, 0x18b3583a, 0x1d442ef7 };

uint64_t bs64[] = { 0x51fa6d2b67ea7b29, 0x4bd37f8073b73f28, 0x7e8140cb759833c9, 0x1867403a575c07cf,
                    0x1644787222171461, 0x40317cda0a6c7a54, 0x184e6b3453b306db, 0x7b676ab967294d62,
                    0x57e44f13488b23b8, 0x4e933c4262e04d14, 0x50ac3f5c435910dd, 0x3c364dc50b315484 };


int popcnt16_p(uint16_t b) {
    int n = 0;
    uint16_t mask;
    for (mask = 1; mask != 0; mask <<= 1) if (b & mask) n++;
    return n;
}

int popcnt32_p(uint32_t b) {
    int n = 0;
    uint32_t mask;
    for (mask = 1; mask != 0; mask <<= 1) if (b & mask) n++;
    return n;
}

int popcnt64_p(uint64_t b) {
    int n = 0;
    uint64_t mask;
    for (mask = 1; mask != 0; mask <<= 1) if (b & mask) n++;
    return n;
}


int popcnt16(uint16_t b) {
    b = (b & 0x5555) + (b >> 1 & 0x5555);
    b = (b & 0x3333) + (b >> 2 & 0x3333);
    b = (b & 0x0f0f) + (b >> 4 & 0x0f0f);
    b = (b & 0x00ff) + (b >> 8 & 0x00ff);
    return b;
}

int popcnt32(uint32_t b) {
    b = (b & 0x55555555) + (b >> 1 & 0x55555555);
    b = (b & 0x33333333) + (b >> 2 & 0x33333333);
    b = (b & 0x0f0f0f0f) + (b >> 4 & 0x0f0f0f0f);
    b = (b & 0x00ff00ff) + (b >> 8 & 0x00ff00ff);
    b = (b & 0x0000ffff) + (b >> 16 & 0x0000ffff);
    return b;
}

int popcnt64(uint64_t b) {
    b = (b & 0x5555555555555555) + (b >> 1 & 0x5555555555555555);
    b = (b & 0x3333333333333333) + (b >> 2 & 0x3333333333333333);
    b = (b & 0x0f0f0f0f0f0f0f0f) + (b >> 4 & 0x0f0f0f0f0f0f0f0f);
    b = (b & 0x00ff00ff00ff00ff) + (b >> 8 & 0x00ff00ff00ff00ff);
    b = (b & 0x0000ffff0000ffff) + (b >> 16 & 0x0000ffff0000ffff);
    b = (b & 0x00000000ffffffff) + (b >> 32 & 0x00000000ffffffff);
    return b;
}


int main(void) {
    int i;

    printf("========== 16 bit ==========\n");
    for (i = 0; i < 10; i++)
        printf("%04x: popcnt %2d popcnt_p %2d\n", bs16[i], popcnt16(bs16[i]), popcnt16_p(bs16[i]));

    printf("========== 32 bit ==========\n");
    for (i = 0; i < 10; i++)
        printf("%08x: popcnt %2d popcnt_p %2d\n", bs32[i], popcnt32(bs32[i]), popcnt32_p(bs32[i]));

    printf("========== 64 bit ==========\n");
    for (i = 0; i < 10; i++)
        printf("%016lx: popcnt %2d popcnt_p %2d\n", bs64[i], popcnt64(bs64[i]), popcnt64_p(bs64[i]));

    return 0;
}