なつたん

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

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をタイムシェアリングすれば、
もっと少なく行けそうですね。