Author: Alessandro Damiani
Date: 17:41:28 09/13/99
Go up one level in this thread
On September 13, 1999 at 17:59:49, Robert Hyatt wrote:
>On September 13, 1999 at 10:06:43, Alessandro Damiani wrote:
>
>>On September 13, 1999 at 09:33:27, stefan wrote:
>>
>>>On September 13, 1999 at 09:01:22, Alessandro Damiani wrote:
>>>
>>>>On September 13, 1999 at 08:25:35, Daniel Clausen wrote:
>>>>
>>>>>Hi
>>>>>
>>>>>On September 13, 1999 at 07:56:01, Alessandro Damiani wrote:
>>>>>
>>>>>>On September 13, 1999 at 04:48:40, stefan wrote:
>>>>>
>>>>>[snip]
>>>>>>or in C:
>>>>>>
>>>>>>{
>>>>>> n= 0; y= 1;
>>>>>> while (y<X) {
>>>>>> n++; y+= y;
>>>>>> }
>>>>>>}
>>>>>>
>>>>>>You could use binary search, but there are only 64 elements.
>>>>>
>>>>>Welp.. with 64 elements it may be worth it. :)
>>>>>
>>>>>But I would use one of the standard algorithms for the FirstOne-problem.
>>>>>For example:
>>>>>
>>>>>
>>>>>typedef long long BitBoard; // Assuming long long is 64bit wide.
>>>>>
>>>>>typedef union
>>>>>{
>>>>> unsigned short us[4]; // Assuming unsigned short is 16bit wide.
>>>>> BitBoard bb;
>>>>>} BBUnion;
>>>>>
>>>>>
>>>>>/////////////////////////////////////////////////////////////////////
>>>>>// Returns the number of the first 1-bit in the 64bit-word.
>>>>>// Order is from LSB to MSB.
>>>>>// If no 1-bit is found, 64 is returned.
>>>>>/////////////////////////////////////////////////////////////////////
>>>>>int FirstOne64(BitBoard bb)
>>>>>{
>>>>> BBUnion x;
>>>>> x.bb = bb;
>>>>>
>>>>> if(x.us[3]) return firstOne16[x.us[3]];
>>>>> else if(x.us[2]) return firstOne16[x.us[2]]+16;
>>>>> else if(x.us[1]) return firstOne16[x.us[1]]+32;
>>>>> else if(x.us[0]) return firstOne16[x.us[0]]+48;
>>>>>
>>>>> return 64;
>>>>>}
>>>>>
>>>>>
>>>>>Here firstOne16[] is a simple lookup-array. Since it is indexed with 16bit
>>>>>values the size of the array is 2^16=64k, which seems ok to me considering
>>>>>the speed advantage. (Of course my program still uses ~20% of the whole time
>>>>>in this single function..)
>>>>>
>>>>>Hope this helps.
>>>>>
>>>>>cu,
>>>>> -sargon
>>>>
>>>>This method makes only sense when the FirstOne(.) routine is used elsewhere in
>>>>the programm. Using this method in non-BitBoard programms isn't worth the memory
>>>>cost. I think he needs the nth bit only for the hashtable size?
>>>>
>>>>Alessandro
>>>
>>>
>>>It should be for bitboards.
>>>I try i[bitboard mod 67]
>>
>>But then the question is the FirstOne(.) routine. Daniel Clausen answered with
>>the right one. I think the table look up is the fastest way (on a 32-bit
>>machine).
>>
>>Alessandro
>
>
>Unless you are running on Intel. Then the hardware BSF instruction is much
>faster. And the new 21264 (EV67) has these instructions in hardware too, which
>makes it the way to do this on the 64 bit alpha...
So, AMD's don't have a hardware BSF? Do you care about the hardware you compile
Crafty on? I still use the table look-up without caring about the hardware. I
should change..
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.