Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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 =====

<code cpp>
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;
}
</code>

<WRAP info>
**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: <code>
    * 000 001 011 111 110 101 010 100
</code>
    * The last code requires circulating to the first bit.

</WRAP>

----

===== The de Bruijn sequence of this 8-bit value =====

^bit^pop_lsb^pop_lsb * 0x1D^hash^index^index order^final order^
^:::^:::^:::^(1st 3 bits)^:::^(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|

<WRAP info>
**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.
<code cpp>
constexpr int table [8] = { 1 , 2 , 7 , 3 , 8 , 6 , 5 , 4 };
</code>

  * 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).

</WRAP>

----

===== Explaining the usage of this de Bruijn sequence =====

<code cpp>
constexpr int table [8] = { 1 , 2 , 7 , 3 , 8 , 6 , 5 , 4 };
</code>

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^
^:::^(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|

<WRAP info>
**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.

</WRAP>

----

===== The Magic Number =====

<WRAP info>
**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.

</WRAP>

----

===== Hash Function Calculation  =====

<code>
hash(x) = (x ∗ dEBRUIJN) >> SHIFT
</code>

<WRAP info>
**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.

</WRAP>

----

===== 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