November 11, 2009C++でビット列の性質を求める[Computer]
あまり需要のある話ではないと思いますが、プログラムでビット列を意識しなければならなくなることがありました。ある数がビット列で表現されており、そのうちの一番右にある'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では怒られてしまったのでサンプルからはずしています。 ※関連して、ビット逆転の記事を書きました。 コメント
おはようございます(@^-^@)ソフトウェアの会社においてcやアセンブラなどのプログラミング環境は触れた経験があります(@^-^@)異業種に応用する事により何か新しいおもしろいもの創れるように考えています(@^-^@) Posted by: c : November 15, 2009 11:48 AMコメントする
|
検索君
スポンサード リンク
最近の記事 HDL-AAX2 シャットダウンスクリプ… 曜日を求める(8bit範囲で) Assisted GPS (A-GPS)… HDL-AAX2の修理 ExcelでMarkdownの表を編集 Rubyで確率分布の性質を求めるgem Windowsのcygwin/MSYS2… RubyでGPS姿勢推定 RubyでGPS受信機 boost::math::distrib… E-MailRelay本体更新(ver … RinRuby (Ruby gem fo… RSpecでのexample間共用のイン… 夏休みの工作: ソースコード公開 夏休みの工作: タッチセンサ GPD Pocketに増設したストレージ… GPD Pocketにストレージ増設 GPD Pocket 内蔵USBハブ基板… GPD Pocket 内蔵USBハブ基板 久しぶりの基板作成 自転車用六角穴付き特注ナット Xiaomi Mi Max (Hydro… Xiaomi Redmi Note 3 … Super Sylphide 進捗状況(… Super Sylphide 進捗状況(… かてごり~一覧 Aero & Astro (100) Computer (189) Embedded System (308) Info (14) Mountain (43) Movable Type (28) Movie & Animation (20) Music (9) Photo (47) Site Management (46) Timely (135) Tips (68) 今月かれんだ~ あ~かいぶ 最近のTrackback ダイナミックDNS 3domain.hk… @ 3年落ちのPCでまだまだがんばる日記 9X到着〜インプレ@ 艦船プラモとRCマイクロヘリが好き! USL-5P@ 谷岡のページ (PukiWiki/TrackBack 0.3) [mbed][猫カメラ]猫カメラつづき@ Embedded 脇見運転 [mbed][猫カメラ]mbed + 猫…@ Embedded 脇見運転 MT4 @ ダイナミックで動く画像リサイ…@ wed@ 私がAudionoではなくBlackfi…@ Blackfin空挺団::Blog 【Web】はぐれメタルできたよー@ I'm St'a'dying English ちっとも、作っていない@ 三D坊主 猫カメラ@ 脇見運転 To 『猫カメラ』 試作中 最近のこめんと いきなりのコメント申し訳ありません。
… by まろまろ先輩 @ GPD Pocket 内蔵USBハブ基板 音楽を読み取りする 説明して欲しいですby 榎本待子 @ iPodからPCに曲を転送 Arduino嫌いだわ。
あんなもの見…by Alice @ 僕がArduinoを使わないわけ やや遅い書き込みで失礼します。
別の機…by LOSスマホ @ Xiaomi Mi Max (Hydrogen) の MIUI8 FM Radio (stock) 日本バンド対応 >Bさま
確か当時、そこまで高くなかっ…by fenrir @ MKS Promenade-Ezy ケージ交換 お値段はおいくらでしたか?
私も曲げて…by Bさま @ MKS Promenade-Ezy ケージ交換 >forester3さん
お返事遅くな…by fenrir @ EZUSB Keilからsdccへ、EZUSB.lib等の移植 お世話になります。3年ほど前sdccの…by forester3 @ EZUSB Keilからsdccへ、EZUSB.lib等の移植 以下のものはどうですかねby て @ VBAで泣かないために >tomi9さん
コメント気づくのが遅…by fenrir @ TCM8240MD breakout (i2cで画像取得モジュール) 動作確認完了 りんく集 |