Author: Gerd Isenberg
Date: 06:17:55 09/09/03
Go up one level in this thread
On September 08, 2003 at 18:02:06, Russell Reagan wrote:
>Is there any way to hash a 64-bit bitboard containing any number of 1-bits? I am
>aware of minimal perfect hash function that will work with bitboards containing
>a single 1-bit (using de Bruijn sequences), and there is a non-minimal method
>for bitboards containing two 1-bits (similar to the de Bruijn method), but I am
>not aware of any hash function that will generate a hash key, given a bitboard
>containing any number of 1-bits.
>
>Does anyone know how this might be accomplished?
Hi Russell,
Modulus by fixed point mul approximation on:
http://www.azillionmonkeys.com/qed/adiv.html
For 64bit modulus-function you may try something like this:
unsigned int mod60 (unsigned __int64 a)
{ // 60 = 15 * 2^2
unsigned __int64 lb = 0x11111112 * (a & 0xffffffff);
unsigned __int64 hb = 0x1111111111111112 * (a >> 32);
int modulus = (int) (a - (((hb+lb)>>32)&(-4)) * 15);
return modulus;
}
With 64*64=128bit multiplication (MSC intrinsic for AMD64) only one
multiplication is necessary.
Regards,
Gerd
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.