November 11, 2009

C++でビット列の性質を求める

あまり需要のある話ではないと思いますが、プログラムでビット列を意識しなければならなくなることがありました。ある数がビット列で表現されており、そのうちの一番右にある'1'の位置を求めたいというでした。例えば、20という数を2進数であらわすと、0b00010100なので一番右のビットは右から3番目にある、というような問題です。

すぐに思いつく実装としては、元の数を2で割っていき、はじめて余りが1になる回数を求めればいいわけですが、2で割るというループがあるので、大きな数の場合には時間がかかってしまいます。そういえば以前どこぞのアルゴリズム辞典で、このような問題をスマートに解決していたのをみたことがあったので、いい機会だと思い調べてみました。

結果『ビットを数える・探すアルゴリズム』という、しっかりとした解説があるページに行き着きました。これによると、右から数えて何番目に初めての'1'があるか、という問題は、ある数が何個の'1'を使って表現されているのか、という問題に帰着され(『NTZを求める』の部分)、これはうまく調整されたビットマスクとビットシフト演算、加算を使うことによってループをはるかに節約できるとのことでした。

参考にしたページにあったものが、intの型に固定されていたので、C++風にテンプレートを使って書き改めてみました。コードと使い方のサンプルを以下に掲載します。

部分特殊化を使って、ビットマスクを生成(make_mask)しています。ビットマスクの生成に関するコードは全て定数値なので、コンパイル時に静的に生成されることが期待できると思います。サンプルでは、int(32 bits), short(16 bits), char(8 bits)の型について動作確認をしています。long long int(64bits)についてもVC9で動作確認をとったのですが、codepadでは怒られてしまったのでサンプルからはずしています。

※関連して、ビット逆転の記事を書きました。

13:21 fenrir が投稿 : 固定リンク | | | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/728