C++ でハミング重みを求める

C++

chiwawa-star.hatenablog.com

ここに載ってる『1からNまでの数字を2進数に変換してbit 1 をcountする』って処理をもっと簡単に出来ないのか調べてみました。 こういう『シンボル列中の 0 以外のシンボルの個数』のことをハミング重みというみたいです。 で、まさに『bit 数から 1 の個数を求める』というアルゴリズムがありました。

[コード]

int
popcount(int x){
    x = x - ((x >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
    return (x * 0x0101010101010101) >> 56;
}

#include <iostream>

int
main(){
    std::cout << popcount(100) << std::endl;
    std::cout << popcount(9859712) << std::endl;
    std::cout << popcount(0b10111110) << std::endl;
    return 0;
}

[出力]

3
9
6

[参照]