chess:programming:de_bruijn_sequence
This is an old revision of the document!
Chess - Programming - de Bruijn Sequence
A de Bruijn Sequence can be used to build a “private bitScanForward routine, and to get the LSB (Last Significant Bit).
A chess board is conveniently 8 x 8 squares, and these can be represented by the numbers 0-63, which is a nice fit for a six-bit long De Bruijn sequence.
64-bit De Bruijn Sequences are 64(+5 wrapped)-bit strings, containing 64 overlapping unique sub-strings (ld(64)==6-bits).
- Because multiplying a De Bruijn Sequence with a single bit or power of two value acts like a shift left, this multiply with extracting the upper six bits by shift right 64-6=58 is a well known bitscan-approach to determine the index/position of a single isolated one in a 64-bit word.
The are 67,108,864 == 0x4000000 == 2^26 Sequences with start index 0 and therefore last index 32 (last index requires wrap of the 5 upper bits, which are all zero).
- There are 64 times more sequences by rotating the initial one.
- So in total 2^32 possible 64*6bit De Bruijn Sequences!
De Bruijn Sequence on a Chess Board
References
chess/programming/de_bruijn_sequence.1635432817.txt.gz · Last modified: 2021/10/28 14:53 by peter