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

An 8-bit value has 8 digits.

The position can be represented by 3 bits.
- Log2(8) = 3.

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.

0x1D: 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	index	index order	final order
bit	pop_lsb	pop_lsb * 0x1D	(1st 3 bits)	index	(index + 1)	(bit at index order position)
1	1	0001 1101	000	0	1	1
2	2	0011 1010	001	1	2	2
3	4	0111 0100	011	3	4	3
4	8	1110 1000	111	7	8	7
5	16	1101 0000	110	6	7	6
6	32	1010 0000	101	5	6	5
7	64	0100 0000	010	2	3	7
8	128	1000 0000	100	4	5	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.
index order: The sequence of the numbers.
final order: The bit at the position of the index order.

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

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

This table is made by using the index order to determine the next number from the final order columns.
The de Bruijn sequence must start with the first digit, the 0 element.
- This is to prevent overflow and to allow the whole to circulate naturally during multiplication (left shift operation).

Explaining the usage of this de Bruijn sequence

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

The c++ code above performs the following function.

It takes a number from 1 to 8 to lookup.
It multiplies this number by 0x1D, which is 29 Decimal. This is the Magic Number.
It right-shifts this by 5 to determine the specific bit position of that lookup value.

Lookup	Lookup multiple by the magic number	Right-shifted by the offset
Lookup	(29 in this example)	(5 in this example)
1	29	0
2	58	1
7	203	6
3	87	2
8	232	7
6	174	5
5	145	4
4	116	3

NOTE: This shows that:

A lookup of 1 returns 0, which is the first bit.
A lookup of 2 returns 1, which is the second bit.
A lookup of 3 returns 2, which is the third bit.
…and so on.

Every lookup returns a unique and distinct value.

The Magic Number

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.

Hash Function Calculation

hash(x) = (x ∗ dEBRUIJN) >> SHIFT

NOTE:

N: is the width of the unsigned integer type.
dEBRUIJN: is the appropriate de Bruijn sequence of length to exhaust the combination of characters being used, 0, 1.
SHIFT: Can be calculated using this formula: (int)(N − Log2(N)).
- Using the 8-bit example:
  - Log2(8) = 2.40823996531
  - 8 - 2.40823996531 = 5.59176003469
  - Round down to make an integer results in 5.

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