一个 n 阶超过 k 个符号（并且长度为 k^n 长度）的 De Bruijn 序列具有一个属性，即每个可能的 n 长度单词在其中都显示为连续字符，其中一些具有循环换行。比如在k=2,n=2的情况下，可能的词是00,01,10,11，一个De Bruijn序列是0011。00,01,11出现在里面，10有换行。这个属性自然意味着左移 De Bruijn 序列（乘以 2 的幂）并取其高 n 位会导致每个 2 乘法器的唯一数字。然后你只需要一个查找表来确定它是哪一个。它的工作原理与小于 2 的幂的数字类似，但在这种情况下，幻数不是 De Bruijn 数列，而是一个类比数。定义属性简单地更改为“
构造 De Bruijn 数的一种可能方法是生成 De Bruijn 图的哈密顿路径，维基百科提供了这种图的示例。在这种情况下，节点是 2^5=32 位整数，有向边是它们之间的转换，其中转换是左移和根据边缘标签的二进制或操作，0 或 1。可能是 2^n-1 类型幻数的直接模拟，它可能值得探索，但这不是人们通常构建此类算法的方式。
在实践中，您可能会尝试以不同的方式构建它，特别是如果您希望它以稍微不同的方式表现。例如，在 bit twiddling hacks 页面上实现前导/尾随零数算法只能返回 [0..31] 中的值。它需要额外检查 0 的情况，它有 32 个零。此检查需要分支，并且在某些 CPU 上可能太慢。
我这样做的方式是，我使用 64 个元素的查找表而不是 32 个，生成随机幻数，并为每个人建立一个具有两个输入幂的查找表，检查其正确性（内射性），然后对其进行验证所有 32 位数字。我继续，直到我遇到一个正确的幻数。结果数字不满足“出现每个可能的 n 长度单词”的属性，因为只出现了 33 个数字，这对于所有 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();
}
}