Hamming weight

お金を払っていないので一週間遅れでしか読めないのですが LWN.net Weekly Edition というのを毎週目を通すようにしています。

先週号を一週間遅れで見ていると、 A summary of 2.6.17 API changes と題されたリリース間近の 2.6.17 での主なカーネル API の変更点がリストアップされている記事があり、そのなかで僕が少しまえにした変更について一行ふれられていました。

* A whole set of generic bit operations (find first set, count set bits, etc.) has been added, helping to unify this code across architectures and subsystems.

パッチは Patch: generic bitops からたどってもらえると見れるのですが、ほとんどが単純で地道な作業なのでつまらないと思います。ただし、セットされているビット数を数える速い方法については見る価値はあるかもしれません。

セットされているビット数のことを "Hamming weight" とか "popcount" (population count) といった呼び方をされるようです。たとえば 32-bit の整数の hamming weight は、ひとつひとつビットをチェックして数えていくより、つぎのようにしたほうが少ないステップで計算できます。

static inline unsigned int generic_hweight32(unsigned int w)
{
        unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
        res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
        res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
        res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
        return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
}

まず 32-bit の整数は 32 個の 1-bit ビットフィールドで、それぞれのビットフィールドが 1-bit の hamming weight になっていると考えることができます。つぎに 1-bit ビットフィールドを二組づつ組み合わせて足すと 16 個の 2-bit ビットフィールドは、それぞれのビットフィールドが 2-bit の hamming weight になっています。このようにくりかえしていけば、もとの 1 個の 32-bit フィールドの hamming weight が計算できます。

n-bit の hamming weight は最大でも n で、それを二つ足しても 2 の 2*n 乗より小さいのでそれぞれのステップでオーバフローしてしまうことはないので上のような工夫したマスクをかけて計算できるのですが、もっと工夫するともうちょっと効率的に計算できます。詳しくは linux@horizon.com というひとの証明をご覧ください。

http://lkml.org/lkml/2006/1/31/152