Author: Alessandro Damiani
Date: 07:06:43 09/13/99
Go up one level in this thread
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
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.