ビットを数える - アセンブラで計算 vs テーブル引き vs ハッカー技巧 南洋の大決戦

ggさん（加藤(gg)さんと思います）にコメント欄で提案を頂きましたが、

今回、IBMが送り出した人類の英知とも言うべきバージョン5を加えてみました。
結論から言うと、アセンブラで計算（バージョン３）の大勝利のようです。
はてな記法に合わせて出力させました。
前回最適化オプション無しでしたが、
今回/Otを付けています。

PopCnt32がアセンブラで計算
PopCnt32bが256表を使い回し
PopCnt32cがバージョン5の分岐無し、表引き無し

bとcも大差ないですね。他の人が試した場合ではbよりcが遅かった例もあるようです。

00000000	PopCnt32	0	0.5s
00000000	PopCnt32b	0	1.3s
00000000	PopCnt32c	0	1.2s
00000001	PopCnt32	90000001	0.5s
00000001	PopCnt32b	90000001	1.3s
00000001	PopCnt32c	90000001	1.2s
00000002	PopCnt32	90000001	0.6s
00000002	PopCnt32b	90000001	1.3s
00000002	PopCnt32c	90000001	1.2s
00000003	PopCnt32	180000002	0.7s
00000003	PopCnt32b	180000002	1.3s
00000003	PopCnt32c	180000002	1.2s
00000004	PopCnt32	90000001	0.5s
00000004	PopCnt32b	90000001	1.3s
00000004	PopCnt32c	90000001	1.2s
00000005	PopCnt32	180000002	0.8s
00000005	PopCnt32b	180000002	1.3s
00000005	PopCnt32c	180000002	1.2s
00000006	PopCnt32	180000002	0.7s
00000006	PopCnt32b	180000002	1.3s
00000006	PopCnt32c	180000002	1.2s
00000007	PopCnt32	270000003	0.9s
00000007	PopCnt32b	270000003	1.3s
00000007	PopCnt32c	270000003	1.2s
00000008	PopCnt32	90000001	0.5s
00000008	PopCnt32b	90000001	1.3s
00000008	PopCnt32c	90000001	1.2s
00000009	PopCnt32	180000002	0.6s
00000009	PopCnt32b	180000002	1.3s
00000009	PopCnt32c	180000002	1.2s
0000000a	PopCnt32	180000002	0.6s
0000000a	PopCnt32b	180000002	1.3s
0000000a	PopCnt32c	180000002	1.2s
0000000b	PopCnt32	270000003	0.8s
0000000b	PopCnt32b	270000003	1.3s
0000000b	PopCnt32c	270000003	1.2s
0000000c	PopCnt32	180000002	0.6s
0000000c	PopCnt32b	180000002	1.3s
0000000c	PopCnt32c	180000002	1.2s
0000000d	PopCnt32	270000003	0.7s
0000000d	PopCnt32b	270000003	1.3s
0000000d	PopCnt32c	270000003	1.2s
0000000e	PopCnt32	270000003	0.7s
0000000e	PopCnt32b	270000003	1.3s
0000000e	PopCnt32c	270000003	1.2s
0000000f	PopCnt32	360000004	0.9s
0000000f	PopCnt32b	360000004	1.3s
0000000f	PopCnt32c	360000004	1.2s

ビットベクトルが疎で、ほとんどビットが立ってないと仮定すると、
0〜fまでの間は、
完全にアセンブラで計算が速いようです。

検索するとサイボーズラボの中の人が「ビットを数える」をテーマで書いてましたが、
それもフルビット立った場合とか、32ビットの半分立ってるとか、
明らかにバージョン３に不利な局面を仮定しておいて、バージョン３の負けを宣告してました。
実際に使う場面を想定しないと比較は成り立たないと思う

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#include <time.h> 
#include <sys/types.h>
#include <math.h>
#include <windows.h>

__forceinline unsigned int PopCnt32(unsigned int a)
{
  __asm {
                   mov ecx, dword ptr a
                   xor eax, eax
                   test ecx, ecx
                   jz l1
         l0:       lea edx, [ecx - 1]
                   inc eax
                   and ecx, edx
                   jnz l0
         l1:
         }
}


const int Tbl[256]={
	0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
	3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
	1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
	3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
	2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
	3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
	3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
	4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};

// xは、何ビット１が立っているか
__forceinline unsigned int PopCnt32b(unsigned int x)
{
	return Tbl[((unsigned char*)&x)[0]]+Tbl[((unsigned char*)&x)[1]]+Tbl[((unsigned char*)&x)[2]]+Tbl[((unsigned char*)&x)[3]];
}

__forceinline int PopCnt32c(unsigned int bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}


clock_t t_end;
clock_t t_start;

void main()
{
	long count=90000000;
	int sum=0;
	float thinktime;

	for(int j=0x00000000;j<=0x0000000f;j+=0x00000001)
	{
		t_start = clock();
		sum=0;
		for(long i=0;i<=count;i++)
			sum+=PopCnt32(j);
		t_end = clock();
		thinktime=(float)(t_end - t_start) / CLOCKS_PER_SEC;
		printf("|%08x|PopCnt32 |%d|%4.1fs|\n",j,sum,thinktime );

		t_start = clock();
		int sum=0;
		for(long i=0;i<=count;i++)
			sum+=PopCnt32b(j);
		t_end = clock();
		thinktime=(float)(t_end - t_start) / CLOCKS_PER_SEC;
		printf("|%08x|PopCnt32b|%d|%4.1fs|\n",j,sum,thinktime );

		t_start = clock();
		sum=0;
		for(long i=0;i<=count;i++)
			sum+=PopCnt32c(j);
		t_end = clock();
		thinktime=(float)(t_end - t_start) / CLOCKS_PER_SEC;
		printf("|%08x|PopCnt32c|%d|%4.1fs|\n",j,sum,thinktime );
	}

}

飛び利きがビット1個立ってると仮定すると

00010000	PopCnt32	90000001	0.5s
00010000	PopCnt32b	90000001	1.3s
00010000	PopCnt32c	90000001	1.2s
00010001	PopCnt32	180000002	0.6s
00010001	PopCnt32b	180000002	1.3s
00010001	PopCnt32c	180000002	1.2s
00010002	PopCnt32	180000002	0.6s
00010002	PopCnt32b	180000002	1.3s
00010002	PopCnt32c	180000002	1.2s
00010003	PopCnt32	270000003	0.7s
00010003	PopCnt32b	270000003	1.3s
00010003	PopCnt32c	270000003	1.2s
00010004	PopCnt32	180000002	0.6s
00010004	PopCnt32b	180000002	1.3s
00010004	PopCnt32c	180000002	1.2s
00010005	PopCnt32	270000003	0.7s
00010005	PopCnt32b	270000003	1.3s
00010005	PopCnt32c	270000003	1.2s
00010006	PopCnt32	270000003	0.7s
00010006	PopCnt32b	270000003	1.3s
00010006	PopCnt32c	270000003	1.2s
00010007	PopCnt32	360000004	0.8s
00010007	PopCnt32b	360000004	1.3s
00010007	PopCnt32c	360000004	1.2s
00010008	PopCnt32	180000002	0.6s
00010008	PopCnt32b	180000002	1.3s
00010008	PopCnt32c	180000002	1.2s
00010009	PopCnt32	270000003	0.7s
00010009	PopCnt32b	270000003	1.3s
00010009	PopCnt32c	270000003	1.2s
0001000a	PopCnt32	270000003	0.7s
0001000a	PopCnt32b	270000003	1.3s
0001000a	PopCnt32c	270000003	1.2s
0001000b	PopCnt32	360000004	0.8s
0001000b	PopCnt32b	360000004	1.3s
0001000b	PopCnt32c	360000004	1.2s
0001000c	PopCnt32	270000003	0.7s
0001000c	PopCnt32b	270000003	1.3s
0001000c	PopCnt32c	270000003	1.2s
0001000d	PopCnt32	360000004	0.8s
0001000d	PopCnt32b	360000004	1.3s
0001000d	PopCnt32c	360000004	1.2s
0001000e	PopCnt32	360000004	0.8s
0001000e	PopCnt32b	360000004	1.3s
0001000e	PopCnt32c	360000004	1.2s
0001000f	PopCnt32	450000005	1.0s
0001000f	PopCnt32b	450000005	1.3s
0001000f	PopCnt32c	450000005	1.2s

若干遅くなったけど、それでもアセンブラで計算が速いです
というわけで、Craftyの中の人もバージョン５は辞めて、バージョン３を使った方がいいと思う
特に利き０の時のバージョン３の速さは凄い。
ただ、味方駒全体のbitboardのPopCntみたいな場合は、16個ぐらい立つのでテーブル引いたりの方がいいですね(^^;