随想録

ビットカウント

最近非常に忙しい。仕事の締め切りや期日まで何日あるのか、指折り数えながら過ごす日々である。

CやC++で数えると言えば、ビットを数えることが頭に浮かぶ。いわゆるビットカウントである。もう少し説明すると、コンピュータの中では、数字は全部0か1で表現されており、その1の数を数えることである。例えば、10進数の22なら、コンピュータ内で10110と表現され、ビットカウントは3となる。

int bitcount(unsigned x)
{
    int b;

    for (b = 0; x != 0; x >>= 1)
        if (x & 01) b++;

    return b;
}

int bitcount(unsigned x)
{
    int b;

    for (b = 0; x != 0; x &= x - 1) b++;

    return b;
}

これら以外でも、以前にインターネットなどを通じて知ったいくつものアルゴリズムがあるが、高速化を行うならテーブル参照が良いかもしれない。また、以下のようなアルゴリズムがあることも知った。

int bitcount(unsigned x)
{
    int b;

    for (b = x; x >>= 1; b -= x);

    return b;
}

初めてこのアルゴリズムを見たときは、即座には仕組みが理解できなかった。このようなコードを知るのは嬉しいことである。この日記を読まれている方もどんな仕組みで動いているのか考えてみると楽しめるかも。