1の個数を数える(in assembler)

マイコンなどの低レベル処理をしているとビットを意識した処理を行うことが多いです。パリティ、CRCなどが代表的です。

今回はその仲間である「１となっているビットの個数を数える」方法の高速化を紹介します。

通常は1ビットずつシフトしていきながら、端のビットを調べる方法(※)を使うと思います。ですがジャンプ命令が絡む処理は重いので(特に割り込み中では)、ジャンプ命令を一切使わない方法を紹介します。

bitcount8:
MOV R25, R24
LSR R25
ANDI R25, 0x55
SUB R24, R25
MOV R25, R24
LSR R25
LSR R25
ANDI R24, 0x33
ANDI R25, 0x33
ADD R24, R25
MOV R25, R24
SWAP R25
ANDI R24, 0x0f
ANDI R25, 0x0f
ADD R24, R25
RET

処理の内容は8ビットのデータを2ビットずつ、4ビットずつに区切ってそれぞれの部分で1の個数を求めて合計していくという流れです。

C言語(avr-gcc)から呼び出しても大丈夫なレジスタの使い方なのでそのままコピペして使えます。少し改良すればパリティや16ビット対応も簡単だと思います。

余談：※の方法を使うときはK&Rの演習2-9を参考にすると結構高速になります(ただし、処理系依存性あり)

by Shiozaki