C
ビット演算

ビット1の出現回数を求めるやつ(popcnt)の意味を理解した

任意のビット並びにおけるビット1の出現回数を求めるアイツ。世間一般的にはpopcntの愛称で親しまれているらしいです。。

popcnt(c99)
#include <stdio.h>      
#include <stdint.h>     

uint32_t popcnt(uint32_t x)
{                       
    uint32_t x_ = x;
    x_ = (x_ & 0x55555555) + (x_>>1 & 0x55555555);
    x_ = (x_ & 0x33333333) + (x_>>2 & 0x33333333);
    x_ = (x_ & 0x0f0f0f0f) + (x_>>4 & 0x0f0f0f0f);
    x_ = (x_ & 0x00ff00ff) + (x_>>8 & 0x00ff00ff);
    x_ = (x_ & 0x0000ffff) + (x_>>16 & 0x0000ffff);

    return x_;          
} 

popcntがやらんとしていること

popcntの意図を説明した図を作ってみました。

この図では例として、8ビット長のビット並び1101 1000におけるビット1の数をカウントしています。

popcnt.png

素朴な疑問に対する回答

  • つまり一言で言うと、どういうことなんですか?

ビット並びというのは、それ自体ですでに各ビットが「自ビットの1の数(=1の集計値)」を表現しているわけです(そりゃそーだ)。これを起点として、隣合う集計値同士でペアを組んで、ペアごとの集計値を求めて…という作業を再帰的に適用すれば、最終的に「ビット並び全体のビット1の集計値」を求められるわけです。

  • ビットマスクの意味は何ですか?

「集計値の並びから、各ペアの片方の集計値だけの並びをピックアップする」ことに該当します。

  • なぜ右ビットシフト>>Nしているのですか?

ペアごとの集計値を合計するとき、(集計値を表すビット表現において)上位半分のビット並びをペアの一方、下位半分のビット並びをペアのもう一方と見立てているわけです。

このとき「上位半分のビット並び」をビットマスクで保存しても末尾0並びがくっついているので、ペア同士で加算するためには桁を一番下までずらす(右ビットシフトする)わけです。

  • 足し算の意味は何ですか?

「隣り合う集計値同士を集計する」ことに該当します。二項+演算子の一方のオペランドが「各ペアの右側集計値だけの並び」、もう一方のオペランドが「各ペアの左側集計値だけの並び」に対応します。