Author: Landon Rabern
Date: 10:14:18 07/03/01
Go up one level in this thread
On July 03, 2001 at 06:49:49, stefan wrote:
>On July 02, 2001 at 15:51:56, Landon Rabern wrote:
>
>>On July 01, 2001 at 22:37:16, Robert Hyatt wrote:
>>
>>>On July 01, 2001 at 10:40:42, stefan wrote:
>>>
>>>>But why not n xor (n-1)?
>>>>
>>>>Thanks for your comment.
>>>
>>>
>>>N & N-1 is a well-known trick to clear the rightmost bit of a number. IE
>>>if you take the value 7, then 7 & 6 is 6 (rightmost bit now off). Repeating,
>>>you have 6 left. 6 & 5 is 4. and finally, 4 & 3 is zero and they are all
>>>now off, being cleared one at a time.
>>>
>>>XOR N and N-1 doesn't seem to do anything useful in the context of bitmaps.
>>>
>>>IE if you start off with 7, 7^6 is 1 (the right bit.) If you repeat this
>>>with 6, 6^5 is 3, which doesn't seem important.
>>
>>It just set all the bits up to the first 1 bit and clears all higher bits.
>>Whether or not tis is useful is another question.
>
>I think this should be good for sliding pieces in set all bits up to the
>first blocking piece?
Thats what n xor (n-2^bit) gets you.
Why does he shift the bitBoard down and then xor with x-2 and then shift it back
up. I would think it would be faster to make a couple lookup tables like this:
bitBoard left[64];
bitBoard right[64];
bitBoard j=1;
for(i=0;i<64;i++)
{
if(i%8==7)
left[i]=0;
else
left[i]=j<<(i+1);
if(i%8==0)
right[i]=0;
else
right[i]=j<<(64-i);
}
and then to get the bits of where the rook can move horizontally just do
for left:
allPieces^(allPieces - left[sq])
for right:
reversePieces^(reversePieces - right[sq])
See the trick with x^(x-2) extends to x^(x-4) , etc.
Then you can just use two seperate while loops to pull out the actual moves,
there will be an extra & operation incurred since you need to mask with what you
are attacking seperately.
So you use only a couple K of memory instead of the 128K used by the regular
bitBoard rookMoves[64][256]. Normally you need to do an & and a >> how much
slower would you think an ^ and a - would be? What if done using the MMX
registers?
Maybe it could be faster for horizontal, but how do you get the vertical
bitBoard back to being vertical quickly? And how do you get the 45 degree
rotated back to to where they need to be quickly? hmmm
Regards,
Landon
This page took 0 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.