Author: Robert Hyatt
Date: 19:21:29 09/17/99
Go up one level in this thread
On September 17, 1999 at 17:53:22, Alessandro Damiani wrote:
>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
Most likely a BFS instruction... if it inlines that then it will really be
fast, although notice that you have to do this in two pieces for a 64 bit
word...
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.