Author: stefan
Date: 06:33:27 09/13/99
Go up one level in this thread
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]
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.