Author: Daniel Clausen
Date: 05:25:35 09/13/99
Go up one level in this thread
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 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.