Author: Bas Hamstra
Date: 17:51:53 09/18/99
Go up one level in this thread
On September 17, 1999 at 22:21:29, Robert Hyatt wrote:
>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...
I've seen it. Is is a few assembly instructions, one of them being BSF. You
can't go faster than ffs(). It basically *is* BSF.
If for 64 bits numbers it is probably faster to test a 32 bit number for being
non zero than doing 2 BSF's straightaway.
Regards,
Bas Hamstra.
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.