Как найти показатель степени двойки за 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 Bruijn) над алфавитом {0,1} для подстрок длины k.

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


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

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

Можно заметить, что цикл де Брёйна всегда можно построить. Рассмотрим, например, направленный граф из всевозможных построк длины 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 — число бит в числе.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 49

    +32
    Довольно интересно! Еще бы умножение за O(1) работало
      +2
      Можно взять простое число, не меньшее k, для которого двойка является порождающим элементом мультипликативной группы (например, для k=32 это p=37) и посчитать остаток от деления 2^n на p. Все остатки будут различны, и найти логарифм можно по табличке.
      Ещё на закуску не хватает задачи «найти по числу m его максимальный делитель вида 2^n за время O(1)»
        +2
        найти по числу m его максимальный делитель вида 2^n за время O(1)

        Казалось бы m ^ (m & (m-1)).
          +2
          m&-m
            0
            Оу, так, конечно, красивее, а мой способ работает и для unsigned.
              0
              -m тоже прекрасно работает для unsigned
                0
                Не на всех компиляторах. Undefined behavior.
                  0
                  m-1 для m=0 тоже UB, в этом отношении способы одинаково неправильные
                    0
                    Вроде вполне определенное С++11 [basic.fundamental]:
                    Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number
                    of bits in the value representation of that particular size of integer.
                      0
                      Но -m тоже под этот пункт попадает тогда…
                        0
                        Вроде да, тоже подходит.
          0
          Зачем простое? Достаточно нечётное… Ну и чтоб размер мультипликативной группы >n. Но здесь же обычный бинпоиск;)
            0
            Надо, чтобы порядок двойки в группе был не меньше k. Для составного p это сразу увеличивает его минимальное значение более, чем вдвое: если p=q*r, то его мультипликативная группа — Z_{q-1} x Z_{r-1}, и порядок любого элемента не больше LCM(q-1,r-1)<=(q-1)*(r-1)/2. Так что простое лучше.
              0
              Кстати, в GCC есть __builtin_ffs или __builtin_ctz для решения этой задачи.
          +3
          В таком графе, в каждую вершину входит два ребра и выходит два ребра, а значит существует Эйлеров цикл

          Зануда во мне говорит, что граф еще должен быть связным.

          А вообще спасибо за статью, интересно.
            0
            Как из наличия эйлерова цикла следует наличие гамильтонова?
              +2
              Там в качестве вершин надо брать подстроки длиной k-1. Тогда каждое ребро будет соответствовать подстроке длины k, и эйлеров цикл даст как раз нужную последовательность. Парочка рёбер окажется петлями, но это неважно.
            +2
            Есть карточный фокус, который основан на де Брёйне: www.math.ubc.ca/~anstee/math443/DeBruijnCardTrick.pdf
              +8
              Предположение, что умножение n-битных чисел выполняется за O(1) означает, что n ограничено.
              Но тогда и традиционный двоичный поиск — решение за O(1) (с коэффициентом log n).
                +3
                Если n небольшое, составляем таблицу из 2^n,
                результатов, затем за O(1) выбираем в этой таблице
                по входному числу как индексу.
                  0
                  Очевидно, n=32 или 64. Таблицу уже не составить.
                  +4
                  А количество бит лучше считать как-нибудь так:
                      n=(n&0x55555555)+((n>>1)&0x55555555);
                      n=(n&0x33333333)+((n>>2)&0x33333333);
                      n=(n+(n>>4))&0x0f0f0f0f;
                      n+=n>>8;
                      count=(n+(n>>16))&0xff;
                  
                    +6
                    Пока кто-нибудь не изобретёт 64-битный процессор.
                      0
                      Для 64-битного процессора можно сделать что-то похожее, всяко быстрее того, что предложил автор статьи. А вообще в процессорах обычно есть отдельные инструкции для подобных вещей,
                        0
                        А потом кто-то изобретёт 128-битный процессор. На нём этот код будет продолжать компилироваться без ошибок и предупреждений, но работать не всегда правильно. Как код от Ариан-4 на Ариан-5.

                        А приведённый автором код из книжки Кернигана и Ричи будет продолжать работать без изменений на любом процессоре, от PDP-11 до самых современных. Вне зависимости от набора инструкций. И скорость выполнения у него та же O(1).
                          0
                          Такая совместимость со всеми возможными процессорами нужна наверно разве что ядру линукса. Большинство программ пишется и умирает гораздо быстрее чем живёт одно поколение процессоров.
                            +1
                            Скорее наоборот, такого рода оптимизация имеет смысл разве что в ядре операционной системы или в компиляторе (которые всё равно пишутся или по крайней мере подгоняются под конкретный процессор).

                            А в прикладных программах эти трюки попадают под определение premature optimization.
                              +2
                              Зависит от частоты применения подобного рода функции в прикладной программе. Если я использую это, скажем, для расчёта весов нейросети из тысяч нейронов, оптимизация лишней не будет.
                                0
                                На таком уровне оптимизация имеет смысл на компиляторах, а не на компилируемых программах. Так, поддержка popcount есть как в GCC, так и в Clang. А вот ни один из вышеприведённых способов ни GCC, ни Clang довести до инструкции POPCNT не смогли.
                              0
                              А потом кто-то изобретёт 128-битный процессор.
                              К этому есть какие-то предпосылки? Если 64 бита ещё как-то были оправданы адресацией памяти и расчётами с числами двойной точности, то применения 128-битам в ближайшие лет 20 я лично придумать не могу (даже с учётом предположения о росте требуемых объёмов памяти пропорционально росту вычислительных возможностей по закону Мура).
                                0
                                А всякая криптография? С какой разрядностью ей приходится работать?
                                64 бит не хватает даже чтобы написать «наивную» арифметику по модулю больше, чем 2^32. Или в других ситуациях, когда надо посчитать a*b/c, но не хочется уходить от целых чисел.
                                  +1
                                  А «всякая криптография» у нас уже либо достаточно заоптимизирована, чтобы не замечать её выполнение на текущих процессорах, либо вынесена в отдельные железные модули в случае, если требуется высокая пропускная способность при низкой нагрузке на CPU. Потому для конечных пользователей эта проблема стоит не очень остро даже с учётом запросов бизнеса.
                                  0
                                  вводить 128 бит будут маркетологи, они оправдают, без оглядки на Ваше мнение. Хотя как по мне — давно пора, есть ряд алгоритмов, которые значительно упростятся, имей они такое виртуальное адресное пространство.
                                  0
                                  А приведённый автором код
                                  Автор никакого кода не привёл, только описание алгоритма, и, судя по его описанию, он очень даже зависит от разрядности процессора.
                                    0
                                    Как же не привёл? Вот он:

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

                                    Прямо из Кернигана и Ричи. Процессоров с переменной разрядностью я пока не встречал, так что это константа.
                                      0
                                      Это я запутался, в статье речь идёт про две разные задачи — нахождение количество бит в числе и нахождение степени двойки.
                              0
                              Зачем, если есть popcnt? software.intel.com/en-us/node/512035
                                0
                                Для процессоров без popcnt. За пределами intel тоже есть жизнь.
                                  0
                                  А для арма есть _popcountsi2. Вот поэтому я и писал выше, что это задача компилятора, а не программиста. В GCC и Clang для этого есть __builtin_popcount. Пусть компилятор соберёт оптимальный набор инструкций.
                                    0
                                    Это может быть и кодом для библиотеки поддержки компилятора в том числе. Хотя таблично population count считается несколько быстрее.
                              +5
                              Вообще говоря, сложность какого-то алгоритма имеет смысл только при указании вычислительной модели. Вы посчитали, как я понимаю, для модели RAM, но, увы, для реальных компьютеров все немного хуже — с длиной числа нужно будет считаться (по сути, количество бит числа будет тем самым n). А за счет умножения у вас даже линейной сложности не выйдет.
                                +1
                                Тем не менее, для n=32 или 64 этот алгоритм может работать быстрее «стандартного» на тех процессорах, которые умеют умножать быстро.
                                  0
                                  И это не совсем верно. Важно понимать, что 64-битные процессоры не смогут быстро и верно перемножить два 64-битных числа в общем случае, ведь их произведение будет занимать больше, чем 64 бита. С уверенностью мы можем говорить лишь про n <= 15 и n <= 31 соответственно.

                                  Для таких чисел мы бинпоиском можем определить степень за, соответственно, 4 и 5 сравнений. Вы уверены, что это медленней чем все действия по алгоритму?
                                    +1
                                    Наверное, это будет для вас сюрпризом — но операция mul/imul, примененная к 64х-разрядным операндам, дает 128и-битный результат. Тот факт, что старшая часть чаще всего отбрасывается, обусловлен системой типов языков высокого уровня, но на низком уровне такой проблемы не стоит.
                                      0
                                      под разрядностью процессора как правило понимают разрядность его интерфейса — разрядность адресуемого пространства и разрядность шины. Внутри процессора может твориться все что угодно. Более того, оно там творится, и уже достаточно давно(по крайней мере для x86 семейства)
                                        0
                                        Исключение — 8-битные CPU, которые чаще всего имеет физическую 16-битную шину адреса и адресуют 64KB
                                • UFO just landed and posted this here
                                    0
                                    А мог бы кто-нибудь обяснить что такое «за О(1)»?
                                      0
                                      Асимптотическая оценка времени для алгоритма. O(1) означает асимптотическую константу — т.е. время работы алгоритма ограничено сверху.

                                    Only users with full accounts can post comments. Log in, please.