Как найти показатель степени двойки за O(1) с помощью последовательности де Брёйна

Аперитив

Всем, наверное, известно, как посчитать количество бит в числе. Например, подойдут следующие два способа:

while (n)
{
    ++count;
    n &= (n-1);
}

while (n)
{
    if (n&1)
        ++count;
    n >>= 1;
}

Упражнение: какое в среднем количество операций будет выполнено в первой и во второй реализации?

Блюдо

Пусть у нас есть n-битное число вида 2^i. Нам необходимо найти i за O(1).
Как это сделать? Пусть n = 2^k. Построим последовательность де Брёйна (de Brujin) над алфавитом {0,1} для подстрок длины k.

Что такое последовательность де Брёйна?

Это циклическая последовательность элементов из алфавита, у которой все подстроки длины k различны. Понятно, что длина последовательности де Брёйна не может превосходить 2^k, ведь именно столько существует различных подстрок длины k над алфавитом из двух элементов. Такую последовательность де Брёйна максимальной длины называется циклом де Брёйна.

Давайте попробуем построить цикл де Брёйна для k=3. Например, он может выглядеть вот так: 00010111. Проверим, что все подстроки длины три в этом цикле различны. Подстрока, начинающаяся в позиции 0, будет равна 000, далее идут подстроки 001, 010, 101, 011, 111, 110 (обратите внимание, последовательность циклична) и 110.

Можно заметить, что цикл де Брёйна всегда можно построить. Рассмотрим, например, направленный граф из всевозможных построк длины k, в котором ребро будет существовать тогда и только тогда, когда одну подстроку можно получить из другой путем сдвига на одну позицию влево и приписыванию элемента из алфавита, например, из вершины 001 будут исходить два ребра в вершины 010 и 011. В таком графе, в каждую вершину входит два ребра и выходит два ребра, а значит существует Эйлеров цикл и, следовательно, цикл, соответствующий циклу де Брёйна, всегда существует.

Что это нам дает?

Возьмем и умножим число вида 2^i на последовательность де Брёйна как на число. Что это нам даст? Последовательность де Брейна будет сдвинута на i шагов влево. Рассмотрим старшие k бит произведения. Очевидно, они однозначно определяют i. Сдвинем их на младшие позиции (на n-k) и посмотрим в таблице размера 2^k какой подстроке соответствует позиция в последовательности де Брёйна. Посчитаем таблицу и получим: 000 -> 0, 001 -> 1, 010 -> 2, 011 -> 4, 100 -> 7, 101 -> 3, 110 -> 6, 111 -> 5, то есть получился массив {0, 1, 2, 4, 7, 3, 6, 5}.

Пусть нам на вход поступило число 16. Умножим его на 00010111 = 23, и получим 368. Естественно, нас интересует результат по модулю 2^8 = 256. 368 = 112 mod 256. 112 = 01110000 в двоичной, теперь сдвигаем его на n-k вправо и получим 011, то есть 3. Смотрим в таблицу и видим значение 4 на позиции 3. Значит, 16 = 2^4.

Получили алгоритм, который работает за O(1) по времени и О(n) по памяти, где n — число бит в числе.

Автор: NotImplemented

Источник