Бит-реверсивная перестановка в D

В этой статье мы расскажем вам про одну известную перестановку элементов массива, которая сама по себе редко упоминается и известна в контексте одного из самых популярных алгоритмов – алгоритма быстрого преобразования Фурье.

В прикладной математике, бит-реверсивная перестановка (или перестановка с обращением битов, bit-reversal permutation) является перестановкой элементов последовательности из N элементов, где N = 2^k (т.е само число N является степенью двойки). Она осуществляется путем присвоения элементам последовательности индексов от 0 до N-1 и затем инвертирования порядка битов их двоичного представления, где каждое число представлено k битами, дополненными нулями при необходимости. Также, данная перестановка является инволюцией, т.е повторное ее применение к набору данных восстанавливает исходный порядок элементов, что является очень ценным свойством бит-реверсной перестановки.

Бит-реверсная перестановка применяется в нескольких быстрых алгоритмах, поскольку вычисление перстановки осуществляется за линейное время и требует только простых вычислений на индексах элементов последовательности. Такая перестановка применяется в быстром преобразовании Фурье (первый этап – это такая перестановка, последний этап точно такая же перестановка для возвращения последовательности в исходный порядок) и при генерации последовательностей с низким расхождением.

Как это работает ?

Предположим, у нас есть массив элементов (к примеру, чисел от 0 до N-1) и его размер является степенью двойки, как было указано ранее. Тогда бит-реверсивная перестановка для некоторых N выглядит следующим образом:

В таблице представлены примеры для некоторых последовательно идущих N и таблица может быть продолжена дальше и для остальных степеней двойки.

Рассмотрим последовательность из восьми чисел от 0 до 7 – [0, 1, 2, 3, 4, 5, 6, 7]. Их индексы представляют собой двоичные числа 000, 001, 010, 011, 100, 101, 110 и 111, которые при обращении порядка битов превращаются в 000, 100, 010, 110, 001, 101, 011 и 111. Таким образом, число 0 на позиции 000 отображается в ту же позицию (000), цифра 1 на позиции 001 отображается в пятую позицию (т.е в позицию с номером 100) и т.д., что дает новую последовательность – [0, 4, 2, 6, 1, 5, 3, 7] . Повторное применение той же перестановки к этой новой последовательности возвращает нам исходную последовательность.

Также, данная перестановка обладает еще одним интересным свойством: она может быть получена из перестановки с меньшим размером. Для получения бит-реверсивной перестановки размером 2*N из перестановки размером N элементов требуется взять результат перестановки, удвоить каждый его индекс (обозначим как a), а затем опять взять результат и прибавить к каждому индексу 1 (обозначим как b), и объединить оба результата через конкатенацию: a ~ b. К примеру, упомянутую выше перестановку для 8 элементов можно получить из перестановки для 4 элементов: перестановка четырех элементов – это массив [0, 2, 1, 3] и если удвоить каждый индекс (получим часть a – [0,4, 2, 6]) и также к каждому индексу добавить по 1 (получим часть b – [1, 5, 3, 7]), то совмещение этих последовательностей в одну даст искомую последовательность из 8 элементов.

Реализация бит-реверсной перестановки в D сводится к нескольким функциям: функция для инвертирования порядка битов (делается на базе побитовых операций), функция для определения количества переставляемых битов в некотором числе и функция выполняющая перестановку. С учетом предыдущих описаний, реализация выглядит так:

/// Перестановка битов в числе
uint reverseBits(uint value, uint numberBitsToReverse)
{
    uint reversed;

    for (uint i = 0; i < numberBitsToReverse; i++)
    {
        reversed <<= 1;
        reversed |= value & 1;
        value    >>= 1;
    }

    return reversed;
}


/// Количество лидирующих нулей
uint countLeadingZeros(T)(T x)
{
    if (x == 0) 
    {
        return x.sizeof * 8;
    }

    int count = 0;
    int numBits = x.sizeof * 8;
    
    while (x > 0) 
    {
        x >>= 1;  // Сдвигаем число вправо на один бит
        count++;
    }
    
    return numBits - count;
}


/// Бит-реверсная перестановка массива
void bitReversePermutation(T)(ref T[] array)
{
	auto length = cast(int) array.length;
    //int log2_Length = 31 - iLog2(length);
    int log2_Length = 31 - countLeadingZeros(length);

    for (uint i = 0; i < length; i++)
    {
        int j = reverseBits(i, log2_Length);
        
        if (j > i)
        {
            T temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

Данный код реализует три указанные функции, которые работают следующим образом:

• reverseBits. Эта функция переворачивает биты в заданном числе. Она принимает два аргумента: value – число, которое нужно перевернуть, и numberBitsToReverse – количество битов, которые требуется перевернуть. Она выполняет цикл, в котором сдвигает reversed влево на 1 бит, затем устанавливает младший бит в value в качестве младшего бита reversed, и сдвигает value вправо на 1 бит. Таким образом получается число с перевернутым порядком следования битов.
• countLeadingZeros. Эта функция подсчитывает количество лидирующих нулей в заданном числе x. Если x равно нулю, то возвращается количество битов в типе, хранящем x. В противном случае, выполняется цикл, в котором x сдвигается вправо на 1 бит, и счетчик count увеличивается на 1. После окончания цикла, возвращается разница между количеством битов в типе значения x и значением count.
• bitReversePermutation. Эта функция выполняет бит-реверсивную перестановку элементов массива array. Она сначала определяет количество битов log2_Length, которые требуется перевернуть в индексе элемента массива. Затем она выполняет цикл от 0 до length – 1 и использует функцию reverseBits для получения перевернутого индекса j. Если j больше i, то значения элементов массива array[i] и array[j] меняются местами.

Реализация алгоритма бит-реверсивной перестановки простая, но неочеивдная. Кроме того, мы полагаем, что вполне можно построить алгоритм и на основе сборке перестановки из перестановок меньшей длины, выполнив перестановку рекурсивно. Такая возможность следует из свойств бит-реверсивной перестановки, но мы не уверены в ее эффективности и потому не сделали ее реализацию, оставив ее как упражнение для энтузиастов.

Примеров использования исключительно самой перестановки мы не обнаружили, но она входит в структуру некоторых алгоритмов, среди которых алгоритм Кули-Тьюки, алгоритмы генерации последовательности Ван Дер Корпута и некоторые оценочные механизмы в распределеных вычислениях. Поскольку, бит-реверсивная перестановка входит в структуру известных процедур, то мы и решили кратко рассказать о ней, особенно с учетом того, что в русскоязычных источниках она практически не освещается (даже в википедии статьи нет). А для тех кто, хочет узнать о ней боольше мы прилагаем скромный набор ссылок ниже:

• Статья в английской википедии
• О применении бит-реверсивной перестановке в оценке нижних границ в распределенных вычислениях