[B! bit][アルゴリズム] ryochackのブックマーク

ryochack id:ryochack

bitとアルゴリズムに関するryochackのブックマーク (2)

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

CPU

アルゴリズム

bit
リンク
x86x64 SSE4.2 POPCNT
2. ビットを数える例題ここにいるバイナリアンの数は何人か？机　1 0 0 1 = 0x0A (ビット2個)机　1 1 1 1 = 0x0F (ビット4個)机　1 1 1 0 = 0x0E (ビット3個)机　1 1 1 1 = 0x0F (ビット4個)机　1 1 1 1 = 0x0F (ビット4個)合計 17人 4. (1) popCount 8bit If1 byte あたり 8回条件分岐して bit を数える for (int i = 0; i < n; i++) { if (*x & 0x01) c++; if (*x & 0x02) c++; if (*x & 0x04) c++; if (*x & 0x08) c++; if (*x & 0x10) c++; if (*x & 0x20) c++; if (*x & 0x40) c++; if (*x & 0x80) c++; x
ryochack 2014/01/19
ビットサーチ、ビットを数える

cpu

アルゴリズム

bit
リンク
1