Ответ 1
Последовательность порядка n De Bruijn порядка над k символами (и длины k ^ n) обладает тем свойством, что каждое возможное слово n-length появляется в виде последовательных символов в нем, некоторые из них с циклической упаковкой. Например, в случае k = 2, n = 2, возможными словами являются 00, 01, 10, 11, и последовательность De Bruijn равна 0011. 00, 01, 11 появляется в нем, 10 с упаковкой. Это свойство, естественно, означает, что левое смещение последовательности Де Брейна (умножение на мощность двух) и принятие его верхних n бит приводит к уникальному числу для каждой мощности двух множителей. Тогда вам нужна только таблица поиска, чтобы определить, какой из них она есть. Он работает по аналогичному принципу с числами, которые меньше мощности двух, но магическое число в этом случае не является последовательностью Де Бройна, а аналогом. Определяющее свойство просто меняется на "все возможные n-длинные слова", как сумма первых m подпоследовательностей длины n, mod 2 ^ n ". Это свойство - все, что необходимо для работы алгоритма. Они просто использовали этот класс волшебных чисел для ускорения алгоритма. Я тоже сделал.
Одним из возможных способов построения чисел Де Бройна является генерация гамильтонова траектории графа Де Бройна, Википедия дает пример такого графика. В этом случае узлы представляют собой 2 ^ 5 = 32-битные целые числа, направленные ребра - это переходы между ними, где переход - сдвиг влево и двоичный или операция в соответствии с меткой края 0 или 1. Там может быть быть прямым аналогом магических чисел типа 2 ^ n-1, это может стоить изучить, но это не так, как обычно люди создают такие алгоритмы.
На практике вы можете попытаться построить его по-другому, особенно если вы хотите, чтобы он вел себя несколько иначе. Например, реализация ведущего/конечного числа алгоритмов нулевого уровня на странице бит-скринштейнов может возвращать значения только в [0..31]. Он нуждается в дополнительной проверке для случая 0, который имеет 32 нуля. Эта проверка требует разветвления и может быть слишком медленной на некоторых процессорах.
Как я это сделал, я использовал таблицу поиска из 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();
}
}