Author: Alessandro Damiani
Date: 14:53:22 09/17/99
Go up one level in this thread
On September 17, 1999 at 16:16:39, Robert Hyatt wrote:
>On September 17, 1999 at 15:57:28, Inmann Werner wrote:
>
>>Hello.
>>
>>Implementing bitboards I came to the old and known problem of finding the
>>number of a bit in the bitboard on Intel machines (32 bit).
>>Trying a little around this evening, I came to following routine. It is simple
>>in C, but looking at the assemmbler outcome, I do not know, if it is good.
>>How do you implement such a extreme critical routine?
>>
>>Werner
>>
>>
>>***************
>>//Testroutine, not tuned but readable
>>//hope no silly bug in it :)
>>// hope also, the idea is clear
>>
>>typedef unsigned __int64 BITBOARD;
>>long lookup1[65];
>>BITBOARD teil;
>>
>>init_bits()
>>{
>>int i;
>>BITBOARD a,b,c;
>>long erg;
>>
>>
>> lookup1[0]=0;
>> a=1;
>> teil=67; /*## OK ##*/
>> for(i=1;i<64;i++)
>> {
>> lookup1[i]=erg;
>> a=a<<1;
>> }
>>}
>>
>>long findbit(BITBOARD x)
>>{
>>BITBOARD c;
>>long bitnr,erg;
>>
>> c=x-(x&(x-1));
>> bitnr=c%teil;
>> erg=lookup1[bitnr];
>> return(erg);
>>}
>>******************************************
>
>
>That is not the way to do it. There are two good ways to do this.
>
>One is to take each byte and use that as an index into a table that
>gives the first 1 bit set in a byte with that particular subscript.
>The other is to use the assembly code that is included with crafty so
>you can access the BSF/BSR hardware instructions that are _very_ fast.
Do you know what is hidden behind the ffs(.) routine? On my Celeron it is faster
than the table-lookup.
Alessandro
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.