Как эффективно реализовать побитовое вращение произвольной последовательности?

Question

«Перестановка p из n элементов, определяемых перестановкой индекса p (i) = (i + k) mod n, называется k- вращением ».- Степанов и МакДжонс

std::rotate стал хорошо известным алгоритмом благодаря Шону Родителю , но как эффективно реализовать его для произвольной последовательности битов?Под эффективностью я подразумеваю сведение к минимуму по крайней мере двух вещей: i) количество записей и ii) сложность пространства в наихудшем случае.

То есть входные данные должны быть аналогичны std::rotate, но по битамЯ думаю, вот так:

1. Указатель на память, где начинается битовая последовательность.
2. Трехбитные индексы: first, middle и last.

Тип указателя может быть любым целым без знака, и, предположительно, чем больше, тем лучше.(Boost.Dynamic Bitset называет это «блоком».)

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

По словам Степанова иМакДжонс, поворот на данных произвольного доступа может быть реализован в n + gcd (n, k) назначениях.Алгоритм, который переворачивает каждый поддиапазон с последующим обращением всего диапазона, занимает 3n назначений.(Тем не менее, я согласен с комментариями ниже, что это фактически 2n присваиваний.) Поскольку биты в массиве могут быть доступны случайным образом, я предполагаю, что применяется та же самая оптимальная граница.Каждое назначение обычно требует двух чтений из-за различных смещений поддиапазона, но я меньше беспокоюсь о чтениях, чем о записи.

Существует ли эффективная или оптимальная реализация этого алгоритма в дикой природе с открытым исходным кодом?Если нет, то как можно это сделать?

Я просмотрел Восхищение Хакера и Том 4А Кнута, но не могу найти алгоритм для этого.

Answer 1

Например, используя vector<uint32_t>, легко и достаточно эффективно выполнить часть вращения с дробным элементом самостоятельно за один проход (shift_amount% 32), а затем вызвать std::rotate, чтобы сделать все остальное. Дробная часть проста и работает только со смежными элементами, за исключением концов, поэтому вам нужно запомнить только один частичный элемент во время работы.

Если вы хотите сделать все это самостоятельно, то вы можете выполнить вращение, изменив порядок всего вектора, а затем изменив порядок передней и задней частей. Хитрость в том, чтобы сделать это эффективно, заключается в том, что когда вы обращаете весь вектор в обратном направлении, вы на самом деле не инвертируете бит каждого элемента - вы просто думаете, что из них как в противоположном порядке. Перестановка передней и задней частей сложнее и требует, чтобы вы помнили 4 частичных элемента во время работы.

С точки зрения записи в память или кэш, оба вышеупомянутых метода производят 2N запись. Оптимальное вращение, на которое вы ссылаетесь в вопросе, занимает N , но если вы расширяете его для работы с вращениями дробных слов, то каждая запись занимает два слова, а затем - 2N . Это не дает никаких преимуществ, и я думаю, что это будет сложно.

Тем не менее ... Я уверен, что вы могли бы приблизиться к N записи с фиксированным объемом хранилища регистров, выполнив m слов за раз, но это много кода для простой ротации, и ваше время (или, по крайней мере, мое время :) будет лучше потрачено в другом месте.