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

参考資料

• ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
• その17 ビット演算あれこれ
• ビットを数える・探すアルゴリズム
• おすすめ書籍｜組込みエンジニア向け | ハングスタック

Pythonで確かめる(8ビットの場合のみ)

def count_1s_in_8bits(val):
    val =  (val & 0x55) + ((val >> 1) & 0x55);
    val =  (val & 0x33) + ((val >> 2) & 0x33);
    return (val & 0x0f) + ((val >> 4) & 0x0f);
    
#確認のため別の方法を試す。
#数値を2進数文字列に変えて、数字1の個数を数える。
def sute(val):
    return bin(val).count('1')
    
for i in range(2**8):
    print(i, bin(i), count_1s_in_8bits(i), sute(i))

実行結果

　

VHDLで実装する(8ビットの場合のみ)

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity count_1s_in_8bits is
    port (
        inp: in std_logic_vector(7 downto 0);
        num_1s: out std_logic_vector(3 downto 0)
    );
end entity;

architecture behavior of count_1s_in_8bits is
    signal sute0, sute1, sute2: unsigned(7 downto 0) := (others => '0');
begin
    sute0 <= unsigned(inp);
    sute1 <= (sute0 and x"55") + (( '0' & sute0(7 downto 1)) and x"55");
    sute2 <= (sute1 and x"33") + (("00" & sute1(7 downto 2)) and x"33");
    num_1s <= std_logic_vector(sute2(3 downto 0) + sute2(7 downto 4));
end architecture;

出来上がった回路

わけの分からないアルゴリズムに見えるが要は全部のビットをツリー形式の加算器で加算しているだけのようである。8ビットの場合は3段で済む。

シミュレーション結果