Author: Gerd Isenberg
Date: 07:56:59 05/28/04
Recently i did some google group search ("popcount", "bitcount") and found some
nice "old" tricks to speed up multiple popcounts (David Seal, Terje Mathisen).
The simple idea is, if you have three words (x,y,z) to count, to perform five
bitwise instructions,
oneOrThree = odd(x,y,z); // (x^y)^z
atLeastTwo = maj(x,y,z); // ((x^y)&z) | (x&y)
to safe one popcount:
2*popCount(atLeastTwo) + popCount(oneOrThree);
== popCount(x) + popCount(y) + popCount(z);
If you want to count ones in up to seven words you may pack them in similar
manner in three words, saving up to four popcounts. Or in general
(2**N)-1 may be logarithmic packed into N words for population counting.
Another obvious application of this trick is to get attack count sets from
several disjoint attacks sets. The following source demonstrates how it works
for ten (that's what i need) disjoint attack sets.
Cheers,
Gerd
#include <stdio.h>
#include <stdlib.h>
typedef unsigned __int64 BitBoard;
__forceinline
unsigned int low (BitBoard x) {return (unsigned int) x;}
__forceinline
unsigned int high(BitBoard x) {return (unsigned int) (x>>32);}
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); // count 4-bit groups
h = (h & 0x33333333) + ((h >> 2) & 0x33333333); // count 4-bit groups
l = (l + (l >> 4)) & 0x0f0f0f0f; // count 8-bits groups
h = (h + (h >> 4)) & 0x0f0f0f0f; // count 8-bits groups
return ((h+l) * 0x01010101) >> 24; // sum 8-bit results
}
// some random attack boards
void initDisjointAttacks(BitBoard disjointAtta[10])
{
srand(0);
for (int i = 0; i < 10; i++)
{
disjointAtta[i] = rand();
disjointAtta[i] <<= 16;
disjointAtta[i] |= rand();
disjointAtta[i] <<= 16;
disjointAtta[i] |= rand();
disjointAtta[i] <<= 16;
disjointAtta[i] |= rand();
}
}
__forceinline
BitBoard odd(BitBoard x, BitBoard y, BitBoard z) {
return x^y^z;}
__forceinline
BitBoard maj(BitBoard x, BitBoard y, BitBoard z) {
return ((x^y)&z)|(x&y);}
void determineAttackCounts(BitBoard c[4], const BitBoard a[10])
{
BitBoard t1,t2,u1,u2,v1,v2,w1,w2,x2,y2,y4,z4;
t1 = odd( a[0], a[1], a[2]);
t2 = maj( a[0], a[1], a[2]);
u1 = odd( a[3], a[4], a[5]);
u2 = maj( a[3], a[4], a[5]);
v1 = odd( a[6], a[7], a[8]);
v2 = maj( a[6], a[7], a[8]);
w1 = odd( a[9], t1, u1);
w2 = maj( a[9], t1, u1);
c[0] = odd(v1, w1, 0); // all odds
x2 = maj(v1, w1, 0);
y2 = odd(t2, u2, v2);
y4 = maj(t2, u2, v2);
c[1] = odd(w2, x2, y2);
z4 = maj(w2, x2, y2);
c[2] = odd(y4, z4, 0);
c[3] = maj(y4, z4, 0);
}
int main(int argc, char* argv[])
{
BitBoard disjointAtta[10]; // up to 15
BitBoard attackCounts[4];
int i, pc1 = 0, pc2 = 0;
initDisjointAttacks(disjointAtta);
determineAttackCounts(attackCounts, disjointAtta);
for (i = 0; i < 10; ++i)
{
pc1 += popCount(disjointAtta[i]);
printf("disjointAtta[%d] 0x%08X%08X\n", i,
high(disjointAtta[i]), low(disjointAtta[i]));
}
printf("==================================\n");
for (i = 0; i < 4; ++i)
{
pc2 += popCount(attackCounts[i]) * (1<<i);
printf("attackCounts[%d] 0x%08X%08X\n", i,
high(attackCounts[i]), low(attackCounts[i]));
}
printf("pc1=%d, pc2=%d\n", pc1, pc2);
getchar();
return 0;
}
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.