В этой статье мы расскажем вам про одну известную перестановку элементов массива, которая сама по себе редко упоминается и известна в контексте одного из самых популярных алгоритмов — алгоритма быстрого преобразования Фурье.
В прикладной математике, бит-реверсивная перестановка (или перестановка с обращением битов, bit-reversal permutation) является перестановкой элементов последовательности из N элементов, где N = 2k (т.е само число N является степенью двойки). Она осуществляется путем присвоения элементам последовательности индексов от 0 до N-1 и затем инвертирования порядка битов их двоичного представления, где каждое число представлено k битами, дополненными нулями при необходимости. Также, данная перестановка является инволюцией, т.е повторное ее применение к набору данных восстанавливает исходный порядок элементов, что является очень ценным свойством бит-реверсной перестановки.
Бит-реверсная перестановка применяется в нескольких быстрых алгоритмах, поскольку вычисление перстановки осуществляется за линейное время и требует только простых вычислений на индексах элементов последовательности. Такая перестановка применяется в быстром преобразовании Фурье (первый этап — это такая перестановка, последний этап точно такая же перестановка для возвращения последовательности в исходный порядок) и при генерации последовательностей с низким расхождением.
Как это работает ?
Предположим, у нас есть массив элементов (к примеру, чисел от 0 до N-1) и его размер является степенью двойки, как было указано ранее. Тогда бит-реверсивная перестановка для некоторых N выглядит следующим образом:
| k | N = 2k | Массив после перестановки |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2 | 0 1 |
| 2 | 4 | 0 2 1 3 |
| 3 | 8 | 0 4 2 6 1 5 3 7 |
| 4 | 16 | 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 |
В таблице представлены примеры для некоторых последовательно идущих 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] меняются местами.
Реализация алгоритма бит-реверсивной перестановки простая, но неочеивдная. Кроме того, мы полагаем, что вполне можно построить алгоритм и на основе сборке перестановки из перестановок меньшей длины, выполнив перестановку рекурсивно. Такая возможность следует из свойств бит-реверсивной перестановки, но мы не уверены в ее эффективности и потому не сделали ее реализацию, оставив ее как упражнение для энтузиастов.
Примеров использования исключительно самой перестановки мы не обнаружили, но она входит в структуру некоторых алгоритмов, среди которых алгоритм Кули-Тьюки, алгоритмы генерации последовательности Ван Дер Корпута и некоторые оценочные механизмы в распределеных вычислениях. Поскольку, бит-реверсивная перестановка входит в структуру известных процедур, то мы и решили кратко рассказать о ней, особенно с учетом того, что в русскоязычных источниках она практически не освещается (даже в википедии статьи нет). А для тех кто, хочет узнать о ней боольше мы прилагаем скромный набор ссылок ниже: