ビットを数える・探すアルゴリズム

作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを

[syd_syd]

すげーっすね / Coqとかで証明してみたいが / s/training/trailing/

[naga_sawa]

ビット演算魔術

[tyru]

すごい

[kanehama]

バージョン4で同じくショックを受ける。どういう脳みそしたら思いつくんだ。

[y_uuki]

POPCNT命令

[wtatsuru]

『ハッカーのたのしみ』おもしろい

[techboon]

4から先は頭が数学者な人が考えないと出てこない気がして、憧れは抱けど自分には日常でニーズがないから入門できない分野。でも楽しそう。

[takoashi_net]

たのしい。こんなことだけ考えたい

[riocampos2]

ループせずにビットカウントできる方法はすばらしいですね。ビットシフトというものが強力なツールであるということ。 ビットを数える・探すアルゴリズム

[riocampos]

ループせずにビットカウントできる方法はすばらしいですね。ビットシフトというものが強力なツールであるということ。

[ryochack]

x86でのビットを数える命令は“POPCNT”

[akachochin]

知っているとビットマップの判定するときにすっきり書けたりすることがある。NetBSDのlibcにはpopcount()という関数があるようですね。

[hirose31]

立っているビットの数を数える population count

[masu_mi]

4が理解出来ない…

[Itisango]

バージョン4あたりから何をやっているのか理解できなくなるorz

[atotto]

ふむふむ

[mrkn]

numofbitsはバージョン5の方がバージョン4より分かりやすいよね。

[hitode909]

へー

[hirata_yasuyuki]

Browsing: "ビットを数える・探すアルゴリズム"

[mooz]

ビット演算のテク

[psyq]

便利なビット演算。

[minodisk]

ビット数を数えるアルゴリズム

[Chuck]

HDLで書いて速度を測ってみたい。

[fenrir-naru]

log2を実装したくなることがC言語でもHDLでもあったりするが、そんなときはこれを使うこと

[pekepekesamurai]

ビット数

[nitoyon]

ビット数を数えるアルゴリズムいろいろ。bits &= bits - 1、0x55555555や0x33333333とのAND（Hacker's Delightより）

[kotak]

立っているビットの数を数える、最初に立っているビットの位置を調べるアルゴリズム

[agw]

大変良質な解説がなされている。

[kamipo]

かろうじてバージョン3が分かる程度

[sleepy_yoshi]

1になっているビットを高速に計算する