Author: Gerd Isenberg
Date: 01:37:07 08/14/03
Go up one level in this thread
On August 13, 2003 at 14:10:22, Anthony Cozzie wrote:
>On August 13, 2003 at 12:38:40, Johan Wessfeldt wrote:
>
>>Im developing a chess engine in java and Im done with the move-generation.
>>Ive run a couple of tests and so far so good. No perf-test failures yet! :]
>>
>>Ive discovered my Least significant Bit method is really slowing me down tho..
>>
>>The best Ive come up with so far goes like this:
>>
>>private int lsb(long a){
>>for(int i=63;i>0;i--){
>> if( (a & mask[i] ) == mask[i] ){
>> return i; }
>>}
>>return 0;
>>}
>>
>>where mask[] is a vector of all the combinations.. like mask[0] = 0001, mask[1]
>>= 00010, mask[3] = 00100 ... and so on.
>>
>>Ive tried some well known methods but with no results since Java's long(64 bits)
>>datatype is signed. It messes up the bits..
>>
>>(All datatypes in Java are signed)
>>
>>Anyone have any suggesitons on how to optimize this method?
>
>There have been thousands of posts to this forum about speeding up LSB/MSB, as
>it is embedded all over the place in any bitboard engine.
>
>There is the lookup-table-approach (someone already posted), Walter Faxon's
>bitboard fold, Matt Taylor's De Bruijn floating point multiply, BSF/BSR X86
>instructions, and a ton of others. Just use the search engine. I personally
>use walter's code.
>
>anthony
Hi Anthony,
Matt Taylor's De Bruijn is not floating point multiply but simple integer
multiply - 64-bit with single isolated bit or 32-bit with folded (High^Low)
single isolated bit minus one [| single isolated bit].
Johan's initial lsb-apprach traverses from bit 63 to bit 0. I use it as MSB, in
the simle arithmetical sense that bit 63 is more "significant" than bit 0.
But of course it depends on your coordinate mapping, whether one find bit 0 more
significant than bit 63.
Gerd
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.