Author: Alessandro Damiani
Date: 06:01:22 09/13/99
Go up one level in this thread
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
This page took 0.01 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.