アルゴリズムの小技

与えられた整数のうち、立っているビット数を数えろ、と言われたらどうします？

一番最初に思いつくのは、ビットシフトしていって0になるまで数えるという、素直なやり方でしょう。例えばこんな感じ。

int bitcount(unsigned long n)
{
    for (int c = 0; n; n >>= 1) {
        if (n & 1) {
            ++c;
        }
    }
    return c;
}

間違ってはいないけど、なんとなく遅そう。テーブルを使えばもっと速い。

int bitcount(unsigned long n)
{
    const static unsigned char aa[] = {
        0, 1, 1, 2,
        1, 2, 2, 3,
        1, 2, 2, 3,
        2, 3, 3, 4
    };

    for (int c = 0; n; n >>= 4) {
        c += aa[n & 0xf];
    }

    return c;
}

ちょっと長くなりましたが、一気に4ビットの計算が出来るので、如何にも速そうです。テーブルの大きさが気になるなら、１ニブルに立っているビットが高々4(3ビットであらわせる)であることを利用すれば、テーブルに必要なメモリ量は半分以下に減らせます。

ニブル単位ではなく、バイト単位で計算したり、ループをエンロールするともっと速くなるでしょうが、省略。

さて、どうにもテーブルを使うのは邪道だ、という向きには、次のような小技は如何でしょう(これが本題)。

int bitcount(unsigned long n)
{
    int c = 0;

    while (n) {
        ++c;
        n &= (n - 1);
    }

    return c;
}

解読の楽しみのために解説は省略……とも思ったのですが、簡単に説明しておきます。 (n & (n - 1)) が、立っているビットのうち最下位をクリアするという性質を利用しているわけです(なぜかは自分で考えてみてください)。ビットシフトをしないということが、既存の発想にとらわれていた私にはなかなか思い至らず、思いついたときには「おぉっ」と一人うなってしまったものでした。なお、nビットの整数の場合、平均ループ数はn/2になります。

余談になりますが、IntelのIA64には、最も低い立っているビットまでシフトするという命令があります。 IA64のアセンブラで書けばこんなの一発なわけですね。ま、上記のせこせことした小技も、いずれもO(n)なんで大差ないですね。

とまぁ、これは実は「プログラミング言語C」の演習に載っていたんですね。演習はこんな具合でした：

2の補数系では、x & (x - 1) により、xの右端の1ビットが消える。なぜか説明せよ。この事実を使って、もっと速いbitcountプログラムを書け。

で、全く別の視点からの、ループを使わずビット演算だけで求めるビット数の数え方があります。フィンローダ氏の初級C言語Q&A(15)に、分かりやすい丁寧な解説があります。

アルゴリズムの小技

立っているビット数を数える