Author: Gerd Isenberg
Date: 04:07:12 06/13/04
Go up one level in this thread
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.
Write it binary and look for consecutive overlapped 6-bit strings
0 3 f 0 8 c 5 3 9 2 f 7 5 6 c d
0000001111110000100011000101001110100010111101110101011011001101(00000)
000000
000001
000011 ....
010000
100000
There are 64 unique 6-bit strings representing values from 0..63.
Multiplying this constant with power of two values, e.g. the isolated ls1b
(b&-b ==> 2**0...2**63) is like shifting the de Bruijn bit pattern left, leaving
the upper six bits as a unique number. An unsigned shift right of 64-6 extracts
this number which acts to an index to map the correct bit index.
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.