Author: Gerd Isenberg
Date: 12:16:57 02/28/06
Go up one level in this thread
On February 28, 2006 at 07:07:23, h.g.muller wrote:
>On February 28, 2006 at 02:57:37, Reinhard Scharnagl wrote:
>
>>
>>When I had been working with a 0x88 structure I used to iterate by:
>>
>>coor = ((coor | ~0x77) + 1) & 0x77;
>>
>>thus handling the coordinate bit combinations of 0x77;
>>
>>But your method above is indeed simpler and faster.
>>
>>Reinhard.
>
>In my minimalistic engine micro-Max I use indeed
>
>while(x=(x+9)&~0x88)
>
>to scan the board. There are all kind of tricks to exploit the fact that the ALU
>in your CPU has special harware to do fast carry propagation, like isolating the
>least-significant '1' bit in a word:
>
>x = y & ~(y-1);
or with two's complement:
x = y & -y
>
>The y-1 changes something like 010010011010000000
>into 010010011001111111, (here the carry does the
>work)
>and the bit-clear makes this 000000000010000000.
>
>If you want to count the number of '1' bits in a long word where the '1's are
>very sparse, getting them one by one through this expression and then clearing
>them with
>
>y &= ~x;
>
>before isolating the next is the fastest way.
Yes, the classical popcount loop for rare populations
for (count=0; x; count++) x &= x-1;
Even if i may have rare populations here and there in my program, i only use the
branchless simd within a register (swar) popcount on todays processors.
Longer code - so not so well suited to your micro max ;-)
__forceinline
unsigned int _fastcall popCount (BitBoard bb) {
unsigned int w = (unsigned int)(bb >> 32), v = (unsigned int)bb;
v = v - ((v >> 1) & 0x55555555);
w = w - ((w >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
v = (v + (v >> 4)) & 0x0F0F0F0F;
w = (w + (w >> 4)) & 0x0F0F0F0F;
v = ((v+w) * 0x01010101) >> 24; // mul is fast on amd procs
return v;
}
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.