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 - Using a De Bruijn Sequence ======

Here is a pre-calculatedde Bruijn Sequence.

<code cpp>
int MultiplyDeBruijnBitPositions[64]
{
  0,1,2,4,8,17,34,5,11,23,47,31,63,62,61,59,
  55,46,29,58,53,43,22,44,24,49,35,7,15,30,60,57,
  51,38,12,25,50,36,9,18,37,10,21,42,20,41,19,39,
  14,28,56,48,33,3,6,13,27,54,45,26,52,40,16,32
};

int getLog2_DeBruijn(ulong v)
{
  return MultiplyDeBruijnBitPosition[(ulong)(v * 0x022fdd63cc95386dull) >> 58];
}
</code>

<WRAP info>
**NOTE:**  The conventional power of 2 and square is extremely slow. (100M calculations needs hours).

  *  There are many alternative methods to make this faster, including:
      * **SIMD and SWAR Techniques**:
      * **De_Bruijn Splited 32bits**:
      * **De_Bruijn 64bits version**:
      * **De_Bruijn 128bits version**:

  * The **De_Bruijn 128bits** version is the fastest.

</WRAP>

----

===== Power of 2 using SIMD and SWAR Techniques =====

<code cpp>
ulong NumBits64(ulong x)
{
    return (Ones64(Msb64(x) - 1ul) + 1ul);
}

ulong Msb64(ulong x)
{  
    //http://aggregate.org/MAGIC/
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);
    return(x & ~(x >> 1));
}

ulong Ones64(ulong x)
{
    //https://chessprogramming.wikispaces.com/SIMD+and+SWAR+Techniques
    const ulong k1 = 0x5555555555555555ul;
    const ulong k2 = 0x3333333333333333ul;
    const ulong k4 = 0x0f0f0f0f0f0f0f0ful;
    x = x - ((x >> 1) & k1);
    x = (x & k2) + ((x >> 2) & k2);
    x = (x + (x >> 4)) & k4;
    x = (x * 0x0101010101010101ul) >> 56;
    return x;
}
</code> 

----

===== Power of 2 using De_Bruijn Splited 32bits =====

<code cpp>
int NumBits64(ulong val)
{
    if (val > 0x00000000FFFFFFFFul)
    {
        // Value is greater than largest 32 bit number,
        // so calculate the number of bits in the top half
        // and add 32.
        return 32 + GetLog2_DeBruijn((int)(val >> 32));
    }
    // Number is no more than 32 bits,
    // so calculate number of bits in the bottom half.
    return GetLog2_DeBruijn((int)(val & 0xFFFFFFFF));
}

int GetLog2_DeBruijn(int val)
{
    uint32 v = (uint32)val;
    int r;      // result goes here

    static const int MultiplyDeBruijnBitPosition[32] = 
    {
        0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
        8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
    };

    v |= v >> 1; // first round down to one less than a power of 2 
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;

    r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
    return r;
}
</code>

----

===== Power of 2 using De_Bruijn 64bits version =====

<code cpp>
static readonly int[] bitPatternToLog2 = new int[64] { 
    0, // change to 1 if you want bitSize(0) = 1
    1,  2, 53,  3,  7, 54, 27, 4, 38, 41,  8, 34, 55, 48, 28,
    62,  5, 39, 46, 44, 42, 22,  9, 24, 35, 59, 56, 49, 18, 29, 11,
    63, 52,  6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
    51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
}; // table taken from http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator
static readonly ulong multiplicator = 0x022fdd63cc95386dUL;

public static int bitSize(ulong v) {
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;
    // at this point you could also use popcount to find the number of set bits.
    // That might well be faster than a lookup table because you prevent a 
    // potential cache miss
    if (v == (ulong)-1) return 64;
    v++;
    return MultiplyDeBruijnBitPosition2[(ulong)(v * multiplicator) >> 58];
}
</code>

----

===== Power of 2 using De_Bruijn 128bits version =====

<code cpp>
static readonly int[] bitPatternToLog2 = new int[64] { 
    0, // change to 1 if you want bitSize(0) = 1
    1,  2, 53,  3,  7, 54, 27, 4, 38, 41,  8, 34, 55, 48, 28,
    62,  5, 39, 46, 44, 42, 22,  9, 24, 35, 59, 56, 49, 18, 29, 11,
    63, 52,  6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
    51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
}; // table taken from http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator
static readonly ulong multiplicator = 0x022fdd63cc95386dUL;

public static int bitSize(ulong v) {
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;
    // at this point you could also use popcount to find the number of set bits.
    // That might well be faster than a lookup table because you prevent a 
    // potential cache miss
    if (v == (ulong)-1) return 64;
    v++;
    return MultiplyDeBruijnBitPosition2[(ulong)(v * multiplicator) >> 58];
}
</code>

----

===== References =====

https://stackoverflow.com/a/21888833/1240074

https://stackoverflow.com/a/21889329/1240074

https://stackoverflow.com/a/21888542/1240074