順序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の累乗より1小さい数と同様の原理で機能しますが、この場合のマジックナンバーは、De Bruijnシーケンスではなく、アナログです。定義するプロパティは単に「
De Bruijn数の構築の1つの可能な方法は、De Bruijnグラフのハミルトンパスの生成です。ウィキペディアは、そのようなグラフの例を提供します。この場合、ノードは2 ^ 5 = 32ビット整数であり、有向エッジはノード間の遷移です。遷移は左シフトであり、エッジのラベル（0または1）に応じたバイナリまたは演算です。 2 ^ n-1タイプのマジックナンバーに直接類似しているので、調べる価値があるかもしれませんが、これは人々が通常そのようなアルゴリズムを構築する方法ではありません。
実際には、特に少し異なる方法で動作させたい場合は、別の方法で構築しようとする場合があります。たとえば、ビットをいじるハックページでのゼロの先頭/末尾の数のアルゴリズムの実装は、[0..31]の値のみを返すことができます。32個のゼロがある0の場合は、追加のチェックが必要です。このチェックには分岐が必要であり、一部のCPUでは遅すぎる可能性があります。
私のやり方では、32ではなく64要素のルックアップテーブルを使用してランダムなマジックナンバーを生成し、それぞれについて2つの入力の累乗でルックアップテーブルを作成し、その正確性（単射）をチェックしてから、すべての32ビット数。正しいマジックナンバーに出会うまで続けました。結果として得られる数字は、33の可能な入力すべてに固有の、33の数字のみが表示されるため、「すべての可能なn長の単語が表示される」という特性を満たしません。
徹底的なブルートフォース検索は、特に優れた魔法数がまれな場合は遅く聞こえますが、入力として2つの値の既知の累乗を最初にテストすると、テーブルはすぐにいっぱいになり、拒否は速く、拒否率は非常に高くなります。各マジックナンバーの後でテーブルをクリアする必要があるだけです。本質的に、私はマジックナンバーを構築するために高い棄却率アルゴリズムを利用しました。
結果として得られるアルゴリズムは次のとおりです。
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入力の代わりに、2^n-1入力が機能する可能性があることは想像の域を超えていません。
ここでは、マジックナンバージェネレーターコードの簡略版を作成しました。2つの入力の累乗のみをチェックすると、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();
}
}