Author: Robert Hyatt
Date: 19:15:59 09/13/99
Go up one level in this thread
On September 13, 1999 at 20:41:28, Alessandro Damiani wrote:
>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
AMD's _must_ have BSF/BSR. Because they claim to be Intel compatible, and
those instructions have been in all the pentiums... they have no choice.
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.