Table of Contents

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

An 8-bit value has 8 digits.


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

bitpop_lsbpop_lsb * 0x1Dhashindexindex orderfinal order
(1st 3 bits)(index + 1)(bit at index order position)
110001 1101000011
220011 1010001122
340111 0100011343
481110 1000111787
5161101 0000110676
6321010 0000101565
7640100 0000010237
81281000 0000100454

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.

LookupLookup multiple by the magic numberRight-shifted by the offset
(29 in this example)(5 in this example)
1290
2581
72036
3872
82327
61745
51454
41163

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