Author: Bas Hamstra
Date: 05:46:56 09/14/99
Go up one level in this thread
On September 13, 1999 at 22:15:59, Robert Hyatt wrote:
>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.
Isn't it "pentia" ?
Sorry, couldn't resist :)
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.