This is an old revision of the document!

Chess - Programming - de Bruijn Sequence - 8-bit Example

An 8-bit value has 8 digits.

The position can be represented by 3 bits

Using a de Bruijn sequence

int lsb_pos(std::uint8_t v)
{
  // 1.  Define a De Bruijn Bit Table.
  static constexpr int DeBruijnBitTable[8] = { 1 , 2 , 7 , 3 , 8 , 6 , 5 , 4 };
 
  // 2.  Get the LSB.
  std::uint8_t pop_lsb = (v & -v);
 
  // 3.  Get which Index to use in the De Bruijn Bit Table.
  std::uint8_t hash = std::uint8_t (pop_lsb * 0x1DU) >> 5;
 
  // 4.  Get the specific Table value.
  int r = DeBruijnBitTable[hash];
 
  return r;
}

NOTE: This shows 4 steps:

Step 1: Describes a pre-built De Bruijn Bit Table.
Step 2: Returns the LSB (Least Significant Bit) from the value being checked against.
Step 3: Uses the LSB from Step 2 to determine which Index should be referred to from the De Bruijn Bit Table.
Step 4: Uses the Index from Step 3 to return the actual hash value.

The big question is where do the following come from:

»5: As an 8-bit number can fit into 3-bits, we want to remove the other 5 bits not needed 11111111 » 101 = 111.
- This leaves the most significant 3 bits.

0x1DU: This value has to be calculated through trial-and-error.
- In binary is 00011101. The de Bruijn sequence.
- Using the binary number and look at it 3 characters at a time, it contains all the sequence numbers with are no duplicates:
```
    * 000 001 011 111 110 101 010 100
```
- The last code requires circulating to the first bit.

The de Bruijn sequence of this 8-bit value

bit	pop_lsb	pop_lsb * 0x1D	hash (1st 3 bits)	index
1	1	0001 1101	000	0
2	2	0011 1010	001	1
3	4	0111 0100	011	3
4	8	1110 1000	111	7
5	16	1101 0000	110	6
6	32	1010 0000	101	5
7	64	0100 0000	010	2
8	128	1000 0000	100	4

NOTE: This is a complete hash in which a value with only one bit set is nicely pushed into a 3-bit number.

Using the table above with the index, will return the value of the original pop_lsb.

hash: Uses the first 3 bits from the previous step, pop_lsb * 0x1D.
index: The number represented by the hash.

Prepare an array with the corresponding number of digits at this position.

constexpr int table [8] = { 1 , 2 , 7 , 3 , 8 , 6 , 5 , 4 };

NOTE: Here, the 1D magic number was used.

However there may be other magic numbers that might also work.
As long as a valid De Bruijn sequence is determined that uniquely provides the bit sequences this could be used instead.

References

https://onihusube-hatenablog-com.translate.goog/entry/2019/09/20/230416?_x_tr_sl=ja&_x_tr_tl=en&_x_tr_hl=en&_x_tr_pto=nui,sc

Wiki

Table of Contents

Chess - Programming - de Bruijn Sequence - 8-bit Example

Using a de Bruijn sequence

The de Bruijn sequence of this 8-bit value

References