Author: Gerd Isenberg
Date: 14:43:17 06/14/04
Hi all,
i proudly like to present one application of the De Bruijn generator mentioned
recently, to build a "private" bitscan routine as shown by Gian-Carlo:
http://www.talkchess.com/forums/1/message.html?370092
Simply compile the following small program with a C++ compiler and call the
executable with a parameter, a decimal number in the range of 1 until 134217728
(2**27), e.g. a sequence of digits of your birth date or similar ;-)
The output is a C-routine with a rather unique de Bruijn constant and
appropriate lookup table. Depending on the number it may take a few minutes.
Have fun,
Gerd
#include <stdio.h>
#include <stdlib.h>
typedef unsigned __int64 BitBoard; // long long
class GenBitScan
{
public:
GenBitScan(int match4nth)
{
m_Lock = 0;
m_dBCount = 0;
m_Match4nth = match4nth;
m_Found = false;
findDeBruijn(0, 64-6);
}
private:
BitBoard m_Lock;
int m_dBCount;
int m_Match4nth;
bool m_Found;
void bitScanRoutineFound(BitBoard deBruijn)
{
int index[64], i;
for (i=0; i<64; i++)
index[(deBruijn<<i)>>58] = i;
printf("\nconst BitBoard magic = 0x%08x%08x; // the %d.\n\n",
(int)(deBruijn>>32), (int)(deBruijn), m_dBCount);
printf("const unsigned int magictable[64] =\n{\n");
for (i=0; i<64; i++)
{
if ( (i & 7) == 0 ) printf("\n ");
printf(" %2d,", index[i]);
}
printf("\n};\n\nunsigned int bitScan (BitBoard b) {\n");
printf(" return magictable[((b&-b)*magic) >> 58];\n}\n");
m_Found = true;
}
void findDeBruijn(BitBoard seq, int bidx)
{
int uniqueIdx = (int) (seq>>bidx) & (64-1);
BitBoard uniqueBit = (BitBoard)1 << uniqueIdx;
if ( !m_Found && (m_Lock & uniqueBit) == 0 && uniqueIdx != 64/2 )
{
if ( bidx == 0 )
{
if ( ++m_dBCount == m_Match4nth )
bitScanRoutineFound(seq);
if ( ++m_dBCount == m_Match4nth )
bitScanRoutineFound(seq<<1);
}
else if ( bidx == 1 )
{
m_Lock |= uniqueBit;
findDeBruijn(seq | 1, 0);
m_Lock &= ~uniqueBit;
}
else
{
m_Lock |= uniqueBit;
findDeBruijn(seq, bidx-1);
findDeBruijn(seq | ((BitBoard)1<<(bidx-1)), bidx-1);
m_Lock &= ~uniqueBit;
}
}
}
};
int main(int argc, char* argv[])
{
if (argc < 2)
printf("usage: genBitScan 1 .. %d\n", 1<<27);
else
GenBitScan(atoi(argv[1]));
return 0;
}
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.