de Bruijn-подобная последовательность для `2 ^ n - 1`: как он построен?

Я смотрю на запись , найдите базу журнала 2 N-бита целое число в операциях O (LG (N) с умножением и Найтись от из битных взломов Twiddling .

Я могу легко увидеть, как второй алгоритм в этой записи

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

, которые рассчитывают n = log2 v , где V , как известно, является мощностью 2. В этом случае 0x077CB531 - обычная последовательность de bruijn, а остальное очевидно.

Однако первый алгоритм в этой записи

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;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

выглядит немного более сложно. Начнем с подвязкой V до ближайшего большего 2 ^ N - 1 значение. Это значение 2 ^ n - 1 затем умножено на 0x07C4Acdd , что в этом случае действует так же, как и последовательность DEBRUIJN в предыдущем алгоритме.

Мой вопрос: как мы создаем эту магию 0x07C4ACDD последовательность? Я Как мы создаем последовательность, которую можно использовать для создания уникальных индексов при умножении на 2 ^ N - 1 значение? Для 2 ^ n Учинок Это просто обычная последовательность de bruijn, как мы можем видеть выше, поэтому понятно, где 0x077cb531 . Но как насчет 2 ^ n - 1 Умличик 0x07c4acdd ? Я чувствую, что здесь не хватает что-то очевидное.

P.S. Чтобы уточнить мой вопрос: я не на самом деле не ищу алгоритма для создания этих последовательностей. Я более интересуюсь некоторой более или менее тривиальной собственностью (если кто-то существует), что делает 0x07C4ACDD , как мы хотим, чтобы это было работать. Для 0x077CB531 Свойство, которое делает его работы, довольно очевидно: он содержит все 5-битные комбинации «сохраненные» в последовательности с 1-битным шагом (что в основном является то, что является последовательностью de bruijn).

0x07C4Acdd , с другой стороны, не является последовательностью de bruijn сама по себе. Итак, какая собственность они были стремиться к построению 0x07C4Acdd (помимо неконструктивного «оно должно сделать вышеуказанную работу алгоритма»)? Кто-то придумал вышеуказанный алгоритм как-то. Таким образом, они, вероятно, знали, что подход является жизнеспособным, и что соответствующая последовательность существует. Как они это знали?

Например, если я должен был построить алгоритм для произвольного V , я бы сделал

v |= v >> 1;
v |= v >> 2;
...

сначала. Тогда я бы просто сделал ++ V , чтобы повернуть V в мощность 2 (давайте предположим, что это не переполняется). Тогда я бы применил первый алгоритм. И, наконец, я бы сделал - R , чтобы получить окончательный ответ. Тем не менее, эти люди удалось оптимизировать его: они устранили ведущие ++ V и трейлинг - R - R , просто изменив множитель и переставляя таблицу. Как они узнали, что это возможно? Что такое математика за этой оптимизацией?