Author: Gerd Isenberg
Date: 10:22:05 05/28/04
Go up one level in this thread
It is due to the "optimized" final nibble mask.
Counting 64 bits with both versions, left column value after executing
0xffffffff unsigned int l = low(bb);
0xffffffff unsigned int h = high(bb);
0xaaaaaaaa l -= (l >> 1) & 0x55555555;
0xaaaaaaaa h -= (h >> 1) & 0x55555555;
0x44444444 l = (l & 0x33333333) + ((l >> 2) & 0x33333333);
0x44444444 h = (h & 0x33333333) + ((h >> 2) & 0x33333333);
0x08080808 l = (l + (l >> 4)) & 0x0f0f0f0f;
0x08080808 h = (h + (h >> 4)) & 0x0f0f0f0f;
0x10101010 l += h;
0x00000040 return (l * 0x01010101) >> 24; // sum 8-bit results
0xffffffff unsigned int l = low(bb);
0xffffffff unsigned int h = high(bb);
0xaaaaaaaa l -= (l >> 1) & 0x55555555;
0xaaaaaaaa h -= (h >> 1) & 0x55555555;
0x44444444 l = (l & 0x33333333) + ((l >> 2) & 0x33333333);
0x44444444 h = (h & 0x33333333) + ((h >> 2) & 0x33333333);
0x88888888 l += h; // oups, a few 8s to much
0x01010100 l = (l + (l >> 4)) & 0x0f0f0f0f;
0x00000003 return (l * 0x01010101) >> 24;
You are almost right, but one additional "and" 0x0f0f0f0f is necessary ;-)
int popCount(BitBoard bb)
{
unsigned int l = low(bb);
unsigned int h = high(bb);
l -= (l >> 1) & 0x55555555; // count 2-bit groups
h -= (h >> 1) & 0x55555555; // count 2-bit groups
l = (l & 0x33333333) + ((l >> 2) & 0x33333333)
+ (h & 0x33333333) + ((h >> 2) & 0x33333333);
l = (l & 0x0f0f0f0f) + ((l >> 4) & 0x0f0f0f0f);
return (l * 0x01010101) >> 24;
}
I guess for lot of applications, e.g. counting bishops (x) and knights (y,z)
attacks this five instruction sequence makes sense to improve popCounting
further:
OneOrThree = x^y;
atLeastTwo = x&y;
atLeastTwo |= OneOrThree & z;
OneOrThree ^= z;
Cheers,
Gerd
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.