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

参考:

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

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, hex(i), bin(i), count_1s_in_8bits(i), sute(i), bin(count_1s_in_8bits(i)), bin(sute(i)))