在k个符号（长度为k ^ n）上的n阶De Bruijn序列具有以下特性：每个可能的n长度单词在其中显示为连续字符，其中一些带有循环换行。例如，在k =
2，n = 2的情况下，可能的单词为00、01、10、11，而De
Bruijn序列为0011。其中的00、01、11出现10，带有换行符。此属性自然意味着左移De
Bruijn序列（乘以2的幂）并取其高n位会导致每个2乘幂的唯一数。然后，您只需要一个查找表即可确定它是哪一个。它的工作原理类似于数字小于1的2的幂，但是在这种情况下，幻数不是De
Bruijn序列，而是类似物。定义属性只需更改为“

De Bruijn数的一种可能的构建方法是De Bruijn图的汉密尔顿路径的生成，维基百科提供了这种图的示例。在这种情况下，节点是2 ^ 5 =
32位整数，有向边是它们之间的过渡，其中过渡是向左移动，并且根据边的标签为0或1进行二进制或运算。作为2 ^
n-1型幻数的直接模拟，可能值得探索，但这不是人们通常构造这种算法的方式。

在实践中，您可能会尝试以不同的方式构造它，特别是如果您希望它以不同的方式表现。例如，在twitterd
hacks页面上实现零位的前导/尾数算法的实现只能返回[0..31]中的值。它需要额外检查0的情况，该情况有32个零。此检查需要分支，在某些CPU上可能太慢。

我这样做的方法是，使用64元素的查找表而不是32的查找表，生成随机幻数，然后针对其中的每一个，使用两个输入的幂建立查找表，检查其正确性（内射性），然后对其进行验证所有32位数字。我继续直到遇到正确的幻数。由于只有33个数字出现，所以所得数字不具有“出现每个可能的n长度字”的属性，这对于所有33个可能的输入都是唯一的。

穷举搜索听起来很慢，尤其是在很少有良好的幻数的情况下，但是如果我们首先测试两个值的已知乘方作为输入，该表将很快被填充，拒绝很快，并且拒绝率很高。我们只需要在每个幻数后清除表格即可。本质上，我利用高拒绝率算法来构造幻数。

结果算法是

int32 Integer::numberOfLeadingZeros (int32 x)
{
    static int32 v[64] = {
        32, -1, 1, 19, -1, -1, -1, 27, -1, 24, 3, -1, 29, -1, 9, -1,
        12, 7, -1, 20, -1, -1, 4, 30, 10, -1, 21, -1, 5, 31, -1, -1,
        -1, -1, 0, 18, 17, 16, -1, -1, 15, -1, -1, -1, 26, -1, 14, -1,
        23, -1, 2, -1, -1, 28, 25, -1, -1, 13, 8, -1, -1, 11, 22, 6};
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x *= 0x749c0b5d;
    return v[cast<uint32>(x) >> 26];
}

int32 Integer::numberOfTrailingZeros (int32 x)
{
    static int32 v[64] = {
        32, -1, 2, -1, 3, -1, -1, -1, -1, 4, -1, 17, 13, -1, -1, 7,
        0, -1, -1, 5, -1, -1, 27, 18, 29, 14, 24, -1, -1, 20, 8, -1,
        31, 1, -1, -1, -1, 16, 12, 6, -1, -1, -1, 26, 28, 23, 19, -1,
        30, -1, 15, 11, -1, 25, 22, -1, -1, 10, -1, 21, 9, -1, -1, -1};
    x &= -x;
    x *= 0x4279976b;
    return v[cast<uint32>(x) >> 26];
}

至于您如何知道的问题，他们可能没有。他们像我一样尝试，尝试改变事物。毕竟，可以想象2 ^ n-1个输入而不是具有不同幻数和查找表的2 ^
n个输入可能起作用不是很大的想象力。

在这里，我对我的幻数生成器代码做了简化。如果仅检查两个输入的幂，它将在5分钟内检查所有可能的幻数，找到1024个幻数。检查其他输入是没有意义的，因为无论如何它们都会减少为2
^ n-1形式。不构造表，但是一旦知道了幻数，它就变得微不足道了。

#include <Frigo/all>
#include <Frigo/all.cpp>

using namespace Frigo::Lang;
using namespace std;

class MagicNumberGenerator
{

    public:

        static const int32 log2n = 5;
        static const int32 n = 1 << log2n;
        static const bool tryZero = false;

        MagicNumberGenerator () {}

        void tryAllMagic ()
        {
            for( int32 magic = 0; magic < Integer::MAX_VALUE; magic++ ){
                tryMagic(magic);
            }
            tryMagic(Integer::MAX_VALUE);
            for( int32 magic = Integer::MIN_VALUE; magic < 0; magic++ ){
                tryMagic(magic);
            }
        }

        bool tryMagic (int32 magic)
        {
            //  clear table
            for( int32 i = 0; i < n; i++ ){
                table[i] = -1;
            }
            //  try for zero
            if( tryZero and not tryInput(magic, 0) ){
                return false;
            }
            //  try for all power of two inputs, filling table quickly in the process
            for( int32 i = 0; i < 32; i++ ){
                if( not tryInput(magic, 1 << i) ){
                    return false;
                }
            }
            //  here we would test all possible 32-bit inputs except zero, but it is pointless due to the reduction to 2^n-1 form
            //  we found a magic number
            cout << "Magic number found: 0x" << Integer::toHexString(magic) << endl;
            return true;
        }

        bool tryInput (int32 magic, int32 x)
        {
            //  calculate good answer
            int32 leadingZeros = goodNumberOfLeadingZeros(x);
            //  calculate scrambled but hopefully injective answer
            x |= x >> 1;
            x |= x >> 2;
            x |= x >> 4;
            x |= x >> 8;
            x |= x >> 16;
            x *= magic;
            x = Integer::unsignedRightShift(x, 32 - log2n);
            //  reject if answer is not injective
            if( table[x] != -1 ){
                return table[x] == leadingZeros;
            }
            //  store result for further injectivity checks
            table[x] = leadingZeros;
            return true;
        }

        static int32 goodNumberOfLeadingZeros (int32 x)
        {
            int32 r = 32;
            if( cast<uint32>(x) & 0xffff0000 ){
                x >>= 16;
                r -= 16;
            }
            if( x & 0xff00 ){
                x >>= 8;
                r -= 8;
            }
            if( x & 0xf0 ){
                x >>= 4;
                r -= 4;
            }
            if( x & 0xc ){
                x >>= 2;
                r -= 2;
            }
            if( x & 0x2 ){
                x >>= 1;
                r--;
            }
            if( x & 0x1 ){
                r--;
            }
            return r;
        }

        int32 table[n];

};

int32 main (int32 argc, char* argv[])
{
    if(argc||argv){}
    measure{
        MagicNumberGenerator gen;
        gen.tryAllMagic();
    }
}