1を数える(ハードウェアで)

チェックサムなどで何かと1を数えたいことが多いので。
多分どこかに似たようなコードが存在しているが。

概要

W = 2^Nビット幅の数値Bits中のセットされているビットの数Countを数える関数を
Counter(N)(Bits)
とでもする。

N=0のとき

当然Counter(0) = Bitsである。

N>0のとき

CountはBitsの上半分のCountとBitsの下半分のCountの和に等しい。
(別に半分である必要はないが、キリが良い)
すなわち、

Counter(N)(Bits) 
= Counter(N-1)(Bits[W-1:W/2]) + Counter(N-1)(Bits[W/2-1:0])

Verilogで書いてみる

関数Counterをそのまま回路にすればいい。

module BitCounter#(parameter N=4)
(
    input[(1<<N)-1:0] Bits,
    output[N:0] Count
    );

    if(N == 0) begin
        assign Count = Bits;
    end
    else begin
        localparam Width = 1<<N;
        localparam Half = 1<<(N-1);
        wire[Half-1:0] Hi = Bits[Width-1:Half];
        wire[N-1:0] CHi;
        BitCounter #(.N(N-1))counterH(.Bits(Hi),.Count(CHi));

        wire[Half-1:0] Lo = Bits[Half-1:0];
        wire[N-1:0] CLo;
        BitCounter #(.N(N-1))counterL(.Bits(Lo),.Count(CLo));

        assign Count = CHi + CLo;
    end
endmodule

パクｒ...参考にしたプログラム

x  =   (x & 0x55555555) + (x >> 1 & 0x55555555);
x  =   (x & 0x33333333) + (x >> 2 & 0x33333333);
x  =   (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
x  =   (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
return (x & 0x0000ffff) + (x >>16 & 0x0000ffff);

Hacker's Delight