PopCnt

仕事でintのビット数を数える処理が必要になった。
SSE4あたりではPOPCNTがあるらしいが、そんな新しいCPUとかコンパイラはつかってないのでどんなアルゴリズムがあるか調べてみた。
こんなのがあって

int popcnt1(unsigned int val){
    unsigned int bits = val;
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F);
    bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF);
    bits = (bits & 0x0000FFFF) + (bits >>16 & 0x0000FFFF);
    return bits;
}

これも同じ

int popcnt2(unsigned int val){
    unsigned int bits = val;
    bits = ((bits & 0xAAAAAAAA) >>  1) + (bits & 0x55555555);
	bits = ((bits & 0xCCCCCCCC) >>  2) + (bits & 0x33333333);
	bits = ((bits & 0xF0F0F0F0) >>  4) + (bits & 0x0F0F0F0F);
	bits = ((bits & 0xFF00FF00) >>  8) + (bits & 0x00FF00FF);
	bits = ((bits & 0xFFFF0000) >> 16) + (bits & 0x0000FFFF);
	return bits;
}

アイディアというか考え方はどちらも同じ。
この例だと32bitを2bit毎に足して、結果をその2bit内にためておく。つぎに2bitの結果を2個足して、結果を4bit内にためておく。さらに4bitの結果を2個足して、結果を8bit内にためておく...と続くと。

2bitのデータnのPOPCNTは

popcnt=(n&0b1)+(n>>1&0b1)
n=0のとき00&01+00&01=0
n=1のとき01&01+00&01=1
n=2のとき10&01+01&01=1
n=3のとき11&01+01&01=2

4bitのデータnのPOPCNTは

n1=(n&0b0101)+(n>>1&0b0101)
popcnt=(n1&0b0011)+(n1>>2&0b0011)

n=1のときn1=1+0=1,popcnt=1+0=1
n=2のときn1=0+1=1,popcnt=1+0=1
n=3のときn1=1+1=2,popcnt=1+1=2
n=4のときn1=4+0=1,popcnt=0+1=1
n=5のときn1=5+0=1,popcnt=1+1=2
n=6のときn1=4+1=5,popcnt=1+1=2
n=7のときn1=5+1=6,popcnt=1+2=3
以下続く...