Круговой сдвиг

Круговые сдвиги: математическая концепция и применение в разработке программного обеспечения

Матрицы 8-элементных циклических сдвигов влево и вправо

В комбинаторной математике циклический сдвиг — это операция перестановки записей в кортеже , либо путем перемещения последней записи на первую позицию, при этом сдвигая все остальные записи на следующую позицию, либо путем выполнения обратной операции. Циклический сдвиг — это особый вид циклической перестановки , которая в свою очередь является особым видом перестановки . Формально циклический сдвиг — это перестановка σ n записей в кортеже, такая, что либо

${\displaystyle \sigma (i)\equiv (i+1)}$ по модулю n , для всех записей i = 1, ..., n

или

${\displaystyle \sigma (i)\equiv (i-1)}$ по модулю n , для всех записей i = 1, ..., n .

Результат многократного применения циклических сдвигов к данному кортежу также называется циклическими сдвигами кортежа.

Например, многократное применение циклических сдвигов к четверке ( a , b , c , d ) дает

• ( г , а , б , в ),
• ( в , г , а , б ),
• ( б , в , г , а ),
• ( a , b , c , d ) (исходная четверка),

и затем последовательность повторяется; таким образом, этот четырехкортеж имеет четыре различных циклических сдвига. Однако не все n -кортежи имеют n различных циклических сдвигов . Например, 4-кортеж ( a , b , a , b ) имеет только 2 различных циклических сдвига. Количество различных циклических сдвигов n -кортежа равно , где k является делителем n , что указывает на максимальное количество повторений по всем подшаблонам. ${\displaystyle {\frac {n}{k}}}$

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

Реализация циклических смен

Циклические сдвиги часто используются в криптографии для перестановки битовых последовательностей. К сожалению, многие языки программирования, включая C , не имеют операторов или стандартных функций для циклического сдвига, хотя практически все процессоры имеют побитовые инструкции для этого (например, Intel x86 имеет ROL и ROR). Однако некоторые компиляторы могут предоставлять доступ к инструкциям процессора с помощью встроенных функций . Кроме того, некоторые конструкции в стандартном коде ANSI C могут быть оптимизированы компилятором для инструкции языка ассемблера «rotate» на процессорах, которые имеют такую ​​инструкцию. Большинство компиляторов C распознают следующую идиому и компилируют ее в одну 32-битную инструкцию rotate. ^{[1] [2]}

/* * Операции сдвига в C определены только для значений сдвига, которые * не отрицательны и меньше, чем sizeof(value) * CHAR_BIT. * Маска, используемая с побитовым И (&), предотвращает неопределенное поведение , * когда счетчик сдвига равен 0 или >= ширине беззнакового целого числа. */#include <stdint.h>  // для uint32_t, чтобы получить 32-битные вращения, независимо от размера int. #include <limits.h>  // для CHAR_BIT  uint32_t rotl32 ( uint32_t значение , беззнаковое целое число count ) { const беззнаковое целое число mask = CHAR_BIT * sizeof ( значение ) - 1 ; count &= mask ; return ( значение << count ) | ( значение >> ( - count & mask )); }                              uint32_t rotr32 ( uint32_t значение , беззнаковое целое число count ) { const беззнаковое целое число mask = CHAR_BIT * sizeof ( значение ) - 1 ; count &= mask ; return ( значение >> count ) | ( значение << ( - count & mask )); }                              

Эта безопасная и удобная для компилятора реализация была разработана Джоном Регером ^[3] и доработана Питером Кордесом. ^{[4] [5]}

Часто встречается более простая версия, когда countдиапазон ограничен от 1 до 31 бита:

uint32_t rotl32 ( значение uint32_t , беззнаковое целое число ) { return ( значение << число ) | ( значение >> ( 32 - число )); }                 

Эта версия опасна, поскольку если равен count0 или 32, она запрашивает 32-битный сдвиг, что является неопределенным поведением в стандарте языка C. Однако она, как правило, работает в любом случае, поскольку большинство микропроцессоров реализуют value >> 32либо 32-битный сдвиг (производящий 0), либо 0-битный сдвиг (производящий исходный value), и любой из них дает правильный результат в этом приложении.

Пример

Если бы последовательность бит 0001 0111 была подвергнута циклическому сдвигу на одну битовую позицию... (см. изображения ниже)

Если бы последовательность бит 1001 0110 была подвергнута следующим операциям:

Приложения

Циклические коды — это разновидность блочного кода со свойством, что циклический сдвиг кодового слова всегда даст другое кодовое слово. Это мотивирует следующее общее определение: для строки s над алфавитом Σ пусть shift ( s ) обозначает множество циклических сдвигов s , а для множества строк L пусть shift ( L ) обозначает множество всех циклических сдвигов строк в L . Если L — циклический код, то shift ( L ) ⊆ L ; это необходимое условие для того, чтобы L был циклическим языком . Операция shift ( L ) изучалась в формальной теории языков . Например, если L — контекстно-свободный язык , то shift ( L ) снова контекстно-свободен. ^{[6] [7]} Кроме того, если L описывается регулярным выражением длины n , существует регулярное выражение длины O ( n ³ ), описывающее shift ( L ). ^[8]

Смотрите также

• Переключатель передач
• Циркулянт
• слово Линдона
• Ожерелье — объект, похожий на кортеж , но для которого круговые сдвиги считаются эквивалентными.

Ссылки

1. GCC: «Оптимизация общих конструкций поворота»
2. "Очистка кода объединителя DAG ROTL/ROTR" упоминает, что этот код поддерживает инструкцию "rotate" в CellSPU.
3. Безопасный, эффективный и переносимый Rotate на C/C++
4. Stackoverflow: Лучшие практики для ротаций в C/C++
5. Почти постоянное время вращения, не нарушающее стандарты
6. Т. Ошиба, «Свойство замкнутости семейства контекстно-свободных языков при операции циклического сдвига», Труды IECЕ, 55D :119–122, 1972.
7. А. Н. Маслов, «Операция циклического сдвига для языков», Проблемы передачи информации 9 :333–338, 1973.
8. Грубер, Герман; Хольцер, Маркус (2009). «Языковые операции с регулярными выражениями полиномиального размера». Теоретическая информатика . 410 (35): 3281–3289. doi : 10.1016/j.tcs.2009.04.009 . Zbl  1176.68105..