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 が投稿 : 固定リンク | | このエントリーを含むはてなブックマーク | この記事をdel.icio.usでブックマーク | トラックバック
このエントリーのトラックバックURL: http://fenrir.naruoka.org/mt/mt-tb.cgi/728
コメント

おはようございます(@^-^@)ソフトウェアの会社においてcやアセンブラなどのプログラミング環境は触れた経験があります(@^-^@)異業種に応用する事により何か新しいおもしろいもの創れるように考えています(@^-^@)

Posted by: c : November 15, 2009 11:48 AM
コメントする









名前、アドレスを登録しますか?
(次回以降コメント入力が楽になります)
  • 匿名でのコメントは受け付けておりません。
  • 名前(ハンドル名可)とメールアドレスは必ず入力してください。
  • メールアドレスを表示されたくないときはURLも必ず記入してください。
  • コメント欄でHTMLタグは使用できません。
  • コメント本文に日本語(全角文字)がある程度多く含まれている必要があります。
  • コメント欄内のURLと思われる文字列は自動的にリンクに変換されます。