Круговой сдвиг - Circular shift

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

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

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

или же

${\ Displaystyle \ сигма (я) \ экв (я-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-битную инструкцию поворота.

/*
 * 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));
}

Эта безопасная и удобная для компилятора реализация была разработана Джоном Регером и доработана Питером Кордесом.

Часто встречается более простая версия, когда диапазон 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 была подвергнута следующим операциям:

Приложения

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

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

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

Рекомендации