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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Круговая смена»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2009 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

В комбинаторной математике , A циклический сдвиг представляет собой операцию перестановки записей в кортеж , либо путем перемещения окончательной записи в первой позиции, в то время как перемещение всех других записей в следующую позицию, или путем выполнения обратной операции. Циклический сдвиг - это особый вид циклической перестановки , которая, в свою очередь, представляет собой особый вид перестановки . Формально круговой сдвиг - это перестановка σ 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 различных круговых сдвига. В общем случае число круговых сдвигов в п -кратного может быть любой делитель из п , в зависимости от записей кортежа.

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

Реализация круговых сдвигов [ править ]

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

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

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

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

uint32_t  rotl32  ( uint32_t  значение ,  неподписанные  INT  Количество )  {  возвращение  значение  <<  подсчитывать  |  значение  >>  ( 32  -  количество ); }

Эта версия опасна, потому что, если она countравна 0 или 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 был циклическим языком . Операционный сдвиг ( L ) изучался в теории формального языка . Например, если L - контекстно-свободный язык , тогда shift ( L ) снова контекстно-свободный. ^{[6] [7]} Кроме того, если L описывается регулярным выражением длины n , существует регулярное выражение длины O ( n ³ ), описывающее сдвиг ( L ). ^[8]

См. Также [ править ]

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

Ссылки [ править ]