Круговой сдвиг
Эта статья нуждается в дополнительных цитатах для проверки . ( декабрь 2009 г. ) |
В комбинаторной математике круговой сдвиг — это операция перестановки записей в кортеже либо путем перемещения последней записи в первую позицию, одновременно перемещая все остальные записи в следующую позицию, либо путем выполнения обратной операции. Круговой сдвиг — это особый вид циклической перестановки , которая, в свою очередь, является особым видом перестановки . Формально круговой сдвиг — это перестановка σ n элементов кортежа такая, что либо
- по модулю n для всех записей i = 1,..., n
или
- по модулю n для всех записей i = 1,..., n .
Результат многократного применения циклических сдвигов к данному кортежу также называется циклическими сдвигами кортежа.
Например, многократное применение циклических сдвигов к кортежу из четырех частей ( a , b , c , d ) последовательно дает
- ( д , а , б , в ),
- ( в , г , а , б ),
- ( б , в , г , а ),
- ( a , b , c , d ) (исходная четверка),
а затем последовательность повторяется; Таким образом, эта четверка имеет четыре различных круговых сдвига. Однако не все n -кортежи имеют n различных циклических сдвигов. Например, кортеж из четырех чисел ( a , b , a , b ) имеет только 2 различных круговых сдвига. Число различных круговых сдвигов n -кортежа равно , где k — делитель n . , указывающий максимальное количество повторов по всем подшаблонам
В компьютерном программировании побитовое вращение , также известное как круговой сдвиг, представляет собой побитовую операцию, которая сдвигает все биты своего операнда. В отличие от арифметического сдвига , циклический сдвиг не сохраняет знаковый бит числа и не отличает плавающей запятой числа с показатель степени от его мантиссы . В отличие от логического сдвига , свободные позиции битов не заполняются нулями, а заполняются битами, выдвинутыми из последовательности.
Внедрение круговых смен
[ редактировать ]Циклические сдвиги часто используются в криптографии для перестановки битовых последовательностей. К сожалению, многие языки программирования, включая C , не имеют операторов или стандартных функций для циклического сдвига, хотя практически все процессоры имеют побитовых операций для него инструкции (например, в Intel x86 есть ROL и ROR).Однако некоторые компиляторы могут предоставлять доступ к инструкциям процессора посредством встроенных функций . Кроме того, некоторые конструкции в стандартном коде ANSI C могут быть оптимизированы компилятором для инструкции языка ассемблера «поворот» на процессорах, которые имеют такую инструкцию. Большинство компиляторов C распознают следующую идиому и компилируют ее в одну 32-битную команду вращения. [1] [2]
/* * Операции сдвига в C определяются только для значений сдвига, которые * не являются отрицательными и меньше, чем sizeof(value) * CHAR_BIT. * Маска, используемая с побитовым «и» (&), предотвращает неопределенное поведение *, когда счетчик сдвига равен 0 или >= ширины unsigned int. */ #include <stdint.h> // для uint32_t, чтобы получить 32-битное вращение, независимо от размера int. #include <limits.h> // для CHAR_BIT uint32_t rotl32 ( uint32_t value , unsigned int count ) { const unsigned int Mask = CHAR_BIT * sizeof ( value ) - 1 ; количество &= маска ; возврат ( значение << количество ) | ( значение >> ( - количество и маска )); } uint32_t rotr32 ( uint32_t значение , беззнаковых целых счетчик чисел ) { const беззнаковое целое число маска = CHAR_BIT * sizeof ( значение ) - 1 ; количество &= маска ; возврат ( значение >> количество ) | ( значение << ( - количество и маска )); }
Эта безопасная и удобная для компиляции реализация была разработана Джоном Регером , [3] и доработан Питером Кордесом. [4] [5]
Более простой вариант часто встречается, когда count
ограничен диапазоном от 1 до 31 бита:
uint32_t rotl32 ( uint32_t значение , беззнаковых целых чисел счетчик ) { return ( значение << счетчик ) | ( значение >> ( 32 - количество )); }
Эта версия опасна, поскольку, если count
равно 0 или 32, он запрашивает 32-битный сдвиг, что является неопределенным поведением в стандарте языка C. Однако в любом случае это работает, поскольку большинство микропроцессоров реализуют value >> 32
либо как 32-битный сдвиг (создание 0), либо 0-битный сдвиг (создание исходного значения). value
), и любой из них дает правильный результат в этом приложении.
Пример
[ редактировать ]Если бы битовая последовательность 0001 0111 была подвергнута циклическому сдвигу на одну битовую позицию... (см. изображения ниже)
|
|
Если битовая последовательность 1001 0110 подверглась следующим операциям:
круговой сдвиг влево на 1 позицию: | 0010 1101 |
круговой сдвиг влево на 2 позиции: | 0101 1010 |
круговой сдвиг влево на 3 позиции: | 1011 0100 |
круговой сдвиг влево на 4 позиции: | 0110 1001 |
круговой сдвиг влево на 5 позиций: | 1101 0010 |
круговой сдвиг влево на 6 позиций: | 1010 0101 |
круговой сдвиг влево на 7 позиций: | 0100 1011 |
круговой сдвиг влево на 8 позиций: | 1001 0110 |
круговой сдвиг вправо на 1 позицию: | 0100 1011 |
круговой сдвиг вправо на 2 позиции: | 1010 0101 |
круговой сдвиг вправо на 3 позиции: | 1101 0010 |
круговой сдвиг вправо на 4 позиции: | 0110 1001 |
круговой сдвиг вправо на 5 позиций: | 1011 0100 |
круговой сдвиг вправо на 6 позиций: | 0101 1010 |
круговой сдвиг вправо на 7 позиций: | 0010 1101 |
круговой сдвиг вправо на 8 позиций: | 1001 0110 |
Приложения
[ редактировать ]Циклические коды — это разновидность блочного кода , свойство которого заключается в том, что циклический сдвиг кодового слова всегда приводит к появлению другого кодового слова. Это мотивирует следующее общее определение: для строки s в алфавите Σ пусть сдвиг ( s ) обозначает набор круговых сдвигов s ,и для набора L строк пусть сдвиг ( L ) обозначает набор всех круговых сдвигов строк L. в Если L — циклический код, то сдвиг ( L ) ⊆ L ; это необходимое условие для того, чтобы L был циклическим языком . Операция сдвиг ( L ) изучалась в теории формального языка . Например, если L — контекстно-свободный язык , то сдвиг ( L ) снова будет контекстно-свободным. [6] [7] Кроме того, если L описывается регулярным выражением длины n , существует регулярное выражение длины O ( n 3 ), описывающее сдвиг ( L ). [8]
См. также
[ редактировать ]- Переключатель ствола
- циркулирующий
- Линдон слово
- Ожерелье — объект, похожий на кортеж , но для которого круговые сдвиги считаются эквивалентными.
Ссылки
[ редактировать ]- ^ GCC: «Оптимизация общих конструкций поворота»
- ^ «Очистка в коде объединителя ROTL/ROTR DAG» упоминает, что этот код поддерживает инструкцию «поворот» в CellSPU.
- ^ Безопасное, эффективное и портативное вращение на C/C++
- ^ Stackoverflow: лучшие практики ротации в C/C++
- ^ Почти постоянное вращение по времени, не нарушающее стандарты.
- ^ Т. Ошиба, «Свойство замыкания семейства контекстно-свободных языков при операции циклического сдвига», Transactions of IECE, 55D : 119–122, 1972.
- ^ А. Н. Маслов, «Операция циклического сдвига для языков», Проблемы передачи информации 9 : 333–338, 1973.
- ^ Грубер, Герман; Хольцер, Маркус (2009). «Языковые операции с регулярными выражениями полиномиального размера» (PDF) . Теоретическая информатика . 410 (35): 3281–3289. дои : 10.1016/j.tcs.2009.04.009 . Збл 1176.68105 . Архивировано из оригинала (PDF) 29 августа 2017 г. Проверено 6 сентября 2012 г. .