ビット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の数をカウントしています。

#素朴な疑問に対する回答

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

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

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

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

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

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

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

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

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