セットビットを数える(128bitバージョン)

参考にしたページ
[ビットを数える・探すアルゴリズム](http://www.nminoru.jp/~nminoru/programming/bitcount.html)

***

```c++
uint8_t num_of_bits_1(__uint128_t a)
{
    uint8_t b = 0;
    while (a)
    {
        if (a & 1)
        {
            b++;
        }
        a >>= 1;
    }

    return (b);
}

const int BITS_COUNT_TABLE[256] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

uint8_t num_of_bits_2(const __uint128_t bits)
{
    const uint8_t *const p = reinterpret_cast<const uint8_t *>(&bits);

    return (BITS_COUNT_TABLE[p[0]] +
            BITS_COUNT_TABLE[p[1]] +
            BITS_COUNT_TABLE[p[2]] +
            BITS_COUNT_TABLE[p[3]] +
            BITS_COUNT_TABLE[p[4]] +
            BITS_COUNT_TABLE[p[5]] +
            BITS_COUNT_TABLE[p[6]] +
            BITS_COUNT_TABLE[p[7]] +
            BITS_COUNT_TABLE[p[8]] +
            BITS_COUNT_TABLE[p[9]] +
            BITS_COUNT_TABLE[p[10]] +
            BITS_COUNT_TABLE[p[11]] +
            BITS_COUNT_TABLE[p[12]] +
            BITS_COUNT_TABLE[p[13]] +
            BITS_COUNT_TABLE[p[14]] +
            BITS_COUNT_TABLE[p[15]]);
}

constexpr __uint128_t convert_to_uint128(const uint64_t left, const uint64_t right)
{
    return (static_cast<__uint128_t>(left) << 64 | right);
}

uint8_t num_of_bits_5(__uint128_t bits)
{
    constexpr __uint128_t a = convert_to_uint128(0x5555'5555'5555'5555LLU, 0x5555'5555'5555'5555LLU);
    constexpr __uint128_t b = convert_to_uint128(0x3333'3333'3333'3333LLU, 0x3333'3333'3333'3333LLU);
    constexpr __uint128_t c = convert_to_uint128(0x0F0F'0F0F'0F0F'0F0FLLU, 0x0F0F'0F0F'0F0F'0F0FLLU);
    constexpr __uint128_t d = convert_to_uint128(0x00FF'00FF'00FF'00FFLLU, 0x00FF'00FF'00FF'00FFLLU);
    constexpr __uint128_t e = convert_to_uint128(0x0000'FFFF'0000'FFFFLLU, 0x0000'FFFF'0000'FFFFLLU);
    constexpr __uint128_t f = convert_to_uint128(0x0000'0000'FFFF'FFFFLLU, 0x0000'0000'FFFF'FFFFLLU);
    constexpr __uint128_t g = convert_to_uint128(0x0000'0000'0000'0000LLU, 0xFFFF'FFFF'FFFF'FFFFLLU);

    bits = (bits & a) + (bits >> 1 & a);
    bits = (bits & b) + (bits >> 2 & b);
    bits = (bits & c) + (bits >> 4 & c);
    bits = (bits & d) + (bits >> 8 & d);
    bits = (bits & e) + (bits >> 16 & e);
    bits = (bits & f) + (bits >> 32 & f);
    bits = (bits & g) + (bits >> 64 & g);

    return (bits);
}
```

リテラルで128bitを書こうとするとコンパイラに怒られたので、それの対策で`convert_to_uint128`を経由してる。constexpr指定で怒られていないのでリテラルと同じ処理になってるはず。

ざっくり回してみて、whileで8.8秒、テーブルで0.31秒、ビット演算で0.50秒、くらいだった。ちゃんと計測したわけじゃないけど。
テーブル参照にデメリットがないならテーブルを使うのが良さそう。処理内容も理解しやすいし。

ちなみに、`popcntl`(32bit単位)を使うようなコードの場合、0.23秒くらいだった。テーブル参照しない分早いかな、という感じ。環境依存が強くなるし、popcnt周りはググるとふしぎなわだいがいっぱいでてくるし、テーブルアクセスとさほど差はないので、わざわざアセンブリコード書かなくてもいいかな、と思う。
テーブルアクセスのわかりやすさサイコー!!