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

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

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

\sigma (i)\equiv (i+1)

по модулю n для всех записей i = 1,..., n

или

\sigma (i)\equiv (i-1)

по модулю n для всех записей i = 1,..., n .

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

Например, многократное применение круговых сдвигов к кортежу из четырех частей ( a , b , c , d ) последовательно дает

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

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

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

Внедрение круговых смен

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

/*
 * Shift operations in C are only defined for shift values which are
 * not negative and smaller than sizeof(value) * CHAR_BIT.
 * The mask, used with bitwise-and (&), prevents undefined behaviour
 * when the shift count is 0 or >= the width of unsigned int.
 */

#include <stdint.h>  // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h>  // for CHAR_BIT

uint32_t rotl32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value >> count) | (value << (-count & mask));
}

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

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

uint32_t rotl32 (uint32_t value, unsigned int count) {
    return (value << count) | (value >> (32 - count));
}

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

Пример

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

влево даст: 0010 1110

вправо даст: 1000 1011.

Если битовая последовательность 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 ³), описывающее сдвиг ( 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 г. .

[1] GCC: «Оптимизация общих конструкций поворота»

[2] «Очистка в коде объединителя ROTL/ROTR DAG» упоминает, что этот код поддерживает инструкцию «поворот» в CellSPU.

[3] Безопасное, эффективное и портативное вращение на C/C++

[4] Stackoverflow: лучшие практики ротации в C/C++

[5] Почти постоянное вращение по времени, не нарушающее стандарты.

[6] Т. Ошиба, «Свойство замыкания семейства контекстно-свободных языков при операции циклического сдвига», Transactions of IECE, 55D : 119–122, 1972.

[7] А. Н. Маслов, "Операция циклического сдвига для языков", Проблемы передачи информации 9 : 333–338, 1973.

[8] Грубер, Герман; Хольцер, Маркус (2009). «Языковые операции с регулярными выражениями полиномиального размера» (PDF) . Теоретическая информатика . 410 (35): 3281–3289. дои : 10.1016/j.tcs.2009.04.009 . Збл 1176.68105 . Архивировано из оригинала (PDF) 29 августа 2017 г. Проверено 6 сентября 2012 г. .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]