« Behind Closed Doors | Main | 謹賀新年 »

2006.01.02

populoation count (個体数計算)

ハッカーのたのしみより。

bitの数え上げのアルゴリズム。
シフトをしながら数え上げる方法、テーブルを使う方法、2bitずつ足す方法
など、実用的な物もそうでないアルゴリズムも紹介されている。
2bitずつ足す方法からの最適化は秀逸なので、一読をお勧め。

中で紹介されていた、無意味っぽいアルゴリズム。

pop(x) = -Σ(x <<< i)
<<<はrotate命令で、i=0から、bit幅-1までの足し算。

どういうことかというと、左にrotateしながら足し込んで、2の補数を
取るとビットの数え上げが完了する。rotateの仕組みから行って、右方向
でも左方向でも結果は同じである。

なんでこうなるのかが分からないのですが、例えば8bitでbitが1つだけ
立っている例(1,2,4等)で考えると、順にローテートしていくと、
1,2,4,8,16,32,64,-128になる。全部足し込んで-1、符号を反転させると
1になる。すげー。

納得いかないので、Cでプログラミングしてみる。

0:0
1:1
2:1
3:2
4:1
5:2
6:2
7:3
(省略)
252:6
253:7
254:7
255:8

と、8bit(左)に対して、ちゃんと数え上げてる(右)。
この本を勉強している趣旨としては、Cの小粋なアルゴリズムの
HDL化なので、Veriogで書き直し。

assign rot0 = data[7:0];
assign rot1 = {data[6:0], data[7]};

こんな感じで、rotateデータを作り、

sum <= rot0 + rot1 + rot2 + rot3 + rot4 + rot5 + rot6 + rot7;
popcount <= - sum;
みたいに足し込む。同じようにできた!

これで、リソース問わなければ、1~2CLKで、数え上げ完了だ。

Cのソースと、Veilogソース、テストベンチなどはここ

ちなみにISEで論理合成させると、Adderを8個使う。
最初の8つの足し合わせに7つと(トーナメント方式で足している)、
最後の反転で一つ使っている。Adderをタイムシェアリングすれば、
もっと少なく行けそうですね。

|

« Behind Closed Doors | Main | 謹賀新年 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/7957063

Listed below are links to weblogs that reference populoation count (個体数計算):

« Behind Closed Doors | Main | 謹賀新年 »