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!

About De Bruijn Sequences

De Bruijn Sequence Generator

De Bruijn Sequence on a Chess Board

Get De Bruijn Sequence

Using a De Bruijn Sequence

https://en.wikipedia.org/wiki/De_Bruijn_sequence

https://www.chessprogramming.org/De_Bruijn_Sequence

http://supertech.csail.mit.edu/papers/debruijn.pdf

https://stackoverflow.com/questions/37083402/fastest-way-to-get-last-significant-bit-position-in-a-ulong-c

https://cstheory.stackexchange.com/questions/19524/using-the-de-bruijn-sequence-to-find-the-lceil-log-2-v-rceil-of-an-integer

https://docplayer.net/167480236-Using-de-bruijn-sequences-to-index-a-1-in-a-computer-word-charles-e-leiserson-harald-prokop-keith-h-randall-mit-laboratory-for-computer-science-cam.html