Author: Gerd Isenberg
Date: 06:52:57 06/13/04
Go up one level in this thread
On June 13, 2004 at 07:07:12, Gerd Isenberg wrote:
>On June 13, 2004 at 04:14:46, Tord Romstad wrote:
>
>>On June 12, 2004 at 13:09:30, Gian-Carlo Pascutto wrote:
>>
>>>const BITBOARD magic = 0x03f08c5392f756cdULL;
>>>
>>>const unsigned int magictable[64] = {
>>>0, 1, 12, 2, 13, 22, 17, 3,
>>>14, 33, 23, 36, 18, 58, 28, 4,
>>>62, 15, 34, 26, 24, 48, 50, 37,
>>>19, 55, 59, 52, 29, 44, 39, 5,
>>>63, 11, 21, 16, 32, 35, 57, 27,
>>>61, 25, 47, 49, 54, 51, 43, 38,
>>>10, 20, 31, 56, 60, 46, 53, 42,
>>>9, 30, 45, 41, 8, 40, 7, 6,
>>>};
>>>
>>>unsigned int FindFirst (const BITBOARD b) {
>>> const BITBOARD lsb = b & -b;
>>> return magictable[(lsb * magic) >> 58];
>>>}
>>
>>I've been staring a this code for 15 minutes trying to figure out how it
>>works, but without success.
>>
>>How does the FindFirst function above perform its magic?
>>
>>Tord
>
>0x03f08c5392f756cdULL is one of 2**32 64+5-bit de Bruijn Constants.
^^
oups, only 2**26 64+5-bit de Bruijn sequences
one 4+1 de Bruijn sequence:
0x3:
0011(0)
00 0
01 1
11 3
10 2
two 8+2-bit de Bruijn sequences (N == 8):
0x1d and 0x17:
00011101(00) 00010111(00)
000 0 000 0
001 1 001 1
011 3 010 2
111 7 101 5
110 6 011 3
101 5 111 7
010 2 110 6
100 4 100 4
there are always log2(N) leading zeroes and log2(N)-1 wrapped trailing zeros.
So the last index is always log2(N) + 1, while the first one is zero.
Gerd
--- some program output
1 0x00000001 4-bit deBruijn found
2 0x00000002 8-bit deBruijn found
16 0x00000010 16-bit deBruijn found
2048 0x00000800 32-bit deBruijn found
67108864 0x04000000 64-bit deBruijn found
--- program output end
--- test program to produce that output
#include <stdio.h>
typedef unsigned __int64 BitBoard;
static unsigned int foundCount = 0;
void genDeBruijn(BitBoard seq, int bidx, int nbits)
{
static BitBoard uniqueCheck = 0;
int uniqueIdx = (int) (seq>>bidx) & (nbits-1);
BitBoard uniqueBit = (BitBoard)1 << uniqueIdx;
if ( (uniqueCheck & uniqueBit) == 0 && uniqueIdx != nbits/2 )
{
if ( bidx == 0 )
{
foundCount++;
// if you like to print out all de Bruijn sequences
// printf("%8d. deBruijn 0x%08x%08x\n",
// foundCount, (int)(seq>>32), (int)(seq));
}
else
{
uniqueCheck |= uniqueBit;
if ( bidx == 1 )
{
genDeBruijn(seq|1, 0, nbits);
}
else
{
bidx--;
genDeBruijn(seq| ((BitBoard)1<<bidx), bidx, nbits);
genDeBruijn(seq, bidx, nbits);
}
uniqueCheck &= ~uniqueBit;
}
}
}
void genDeBruijn(int logn)
{
foundCount = 0;
int nbits = 1 << logn;
genDeBruijn(0, nbits-logn, nbits);
printf("%8d 0x%08x %2d-bit deBruijn found\n",
foundCount, foundCount, nbits);
}
// 6 takes a few minutes!
int main(int argc, char* argv[])
{
genDeBruijn(2);
genDeBruijn(3);
genDeBruijn(4);
genDeBruijn(5);
genDeBruijn(6);
return 0;
}
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.