Эффективное обращение к порядку байтов для произвольного числа бит - PullRequest
Новая
       98

Эффективное обращение к порядку байтов для произвольного числа бит

1 голос
/ 25 февраля 2020

У меня есть список длиной 2 ^ n, который индексируется с номерами до 2 ^ n-1, но проблема в том, что я хотел бы изменить порядок списка с помощью побитовой индексации с обратным порядком байтов.

Например, если n = 4, я хочу поменять местами индексы 0001 <-> 1000, 0010 <-> 0100, 0011 <-> 1100 и т. Д. *

Решения I До сих пор рассматривалось только обратное преобразование байтов (меня интересуют биты ) или использование встроенных функций, которые не работают с произвольным числом битов.

Временной способ, которым я сейчас занимаюсь (Python / C ++), - преобразовать каждый индекс в строку, обратить строку назад и преобразовать обратно в индекс, но это кажется очень неэффективным. Что может быть лучше для этого?

1 Ответ

2 голосов
/ 25 февраля 2020

Выполнение перестановки битов на самом деле не требует реверсирования битов каких-либо целых чисел (это, конечно, способ реализовать его, но не лучший вариант). Это связано с тем, что алгоритм, выполняющий фактическую перестановку, не запрашивает произвольные целые числа с обратным битом в произвольном порядке. Было бы хорошо иметь эту последовательность (для n = 4) 

0000
1000
0100
1100
0010
1010
...

Другой прием для генерации этой последовательности использует то, что операция i + 1 переносит младшие значащие установленные биты, делая их все равными нулю, и затем он устанавливает наименее значимый неустановленный бит. Или, другими словами, это похоже на операцию «инвертировать биты, начиная с LSB, но останавливаться после инвертирования первого нуля». Эту операцию можно относительно легко перевернуть битами, нам просто нужно XOR с помощью некоторой маски смежных установленных битов, длина которой может быть найдена путем вычисления __builtin_ctz(i + 1) + 1 (последний +1 должен включать ноль, который изменился на один на счету). Тогда сама маска может быть найдена как N - (N >> maskLength), где N - это размер массива (степень двойки, вычитая сдвинутую версию, устанавливает все биты, начиная с этой более низкой позиции до более высокой позиции).

Например: (не проверено) 

for (uint32_t i = 0, rev = 0; i < N; ++i)
{
    if (i < rev)
        swap(X[i], X[rev]);
    int maskLen = __builtin_ctz(i + 1) + 1;
    rev ^= N - (N >> maskLen);
}

__builtin_ctz для G CC и Clang, для MSV C вы можете использовать _BitScanForward (работает немного по-другому ).

Существует аналогичная уловка, которая использует начальный нулевой счет i ^ (i + 1).

Кстати, если это используется как часть БПФ, вы могли бы рассмотреть возможность использования алгоритмов, которые в этом нет необходимости, например, алгоритм Кули-Тьюки естественного порядка или алгоритм автосортировки Стокхема.

Фактическое обращение произвольного n -битного числа может быть выполнено первым полностью переворачивая и затем сдвигая вправо на 32 - bits (или 64, если было выполнено 64-битное обратное преобразование). Для каждого конкретного n также существует соответствующий особый случай манипуляции с битами, но затем этот n запекается в коде как константа. Использование полного реверса с последующим сдвигом работает для переменной n. Некоторые процессоры могут иметь инструкции, которые помогают с этим, например, ARM (фактически ARMv6T2 и выше) имеет RBIT.

...