Differences

This shows you the differences between two versions of the page.

--- chess:programming:de_bruijn_sequence:8-bit_example [2021/11/30 00:31] – [The de Bruijn sequence of this 8-bit value] peter
+++ chess:programming:de_bruijn_sequence:8-bit_example [2021/11/30 00:53] (current) – [Explaining the usage of this de Bruijn sequence] peter
@@ Line 3: / Line 3: @@
 An 8-bit value has 8 digits.
-  * The position can be represented by 3 bits
+  * The position can be represented by 3 bits.
+    * Log2(8) = 3.
 ----
@@ Line 55: / Line 56: @@
 ^bit^pop_lsb^pop_lsb * 0x1D^hash^index^index order^final order^
-^:::^:::^:::^(1st 3 bits)^:::^(index + 1)^:::^
+^:::^:::^:::^(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|
@@ Line 72: / Line 73: @@
   * **hash**:  Uses the first 3 bits from the previous step, **pop_lsb * 0x1D**.
   * **index**:  The number represented by the hash.
-  * **index order**:  The sequence
+  * **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.
@@ Line 79: / Line 81: @@
 </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>