Author: Robert Hyatt
Date: 14:59:49 09/13/99
Go up one level in this thread
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...
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.