Введение
Круговые сдвиги: математическая концепция и применения в разработке программного обеспечения
В комбинаторной математике круговой сдвиг — это операция перестановки элементов в кортеже, либо путем перемещения последнего элемента в первое положение, при этом сдвигая все остальные элементы на одну позицию вперед, либо путем выполнения обратной операции. Круговой сдвиг является особым видом циклической перестановки, которая, в свою очередь, является особым видом перестановки. Формально, круговой сдвиг — это перестановка σ из n элементов в кортеже, такая что либо
по модулю n, для всех элементов i = 1, …, n,
либо
по модулю n, для всех элементов i = 1, …, n.
modulo n, for all entries i = 1, , n
or
modulo n, for all entries i = 1, , n.
Результат многократного применения круговых сдвигов к заданному кортежу также называется круговыми сдвигами этого кортежа. Например, многократное применение круговых сдвигов к четырехэлементному кортежу (a, b, c, d) последовательно дает
(d, a, b, c),
(c, d, a, b),
(b, c, d, a),
(a, b, c, d) (исходный четырехэлементный кортеж),
а затем последовательность повторяется; этот четырехэлементный кортеж, следовательно, имеет четыре различных круговых сдвига. Однако не все кортежи из n элементов имеют n различных круговых сдвигов. Например, четырехэлементный кортеж (a, b, a, b) имеет только 2 различных круговых сдвига. Число различных круговых сдвигов кортежа из n элементов равно , где k — делитель n, указывающий на максимальное количество повторений по всем подпаттернам. В компьютерном программировании битовое вращение, также известное как круговой сдвиг, — это битовая операция, которая сдвигает все биты своего операнда. В отличие от арифметического сдвига, круговой сдвиг не сохраняет знаковый бит числа и не различает показатель числа с плавающей точкой и его мантиссу. В отличие от логического сдвига, освободившиеся битовые позиции не заполняются нулями, а заполняются битами, которые выходят из последовательности.
(d, a, b, c),
(c, d, a, b),
(b, c, d, a),
(a, b, c, d) (the original four tuple),
and then the sequence repeats; this four tuple therefore has four distinct circular shifts. However, not all n tuples have n distinct circular shifts. For instance, the 4 tuple (a, b, a, b) only has 2 distinct circular shifts. The number of distinct circular shifts of an n tuple is , where k is a divisor of n, indicating the maximal number of repeats over all subpatterns. In computer programming, a bitwise rotation, also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an arithmetic shift, a circular shift does not preserve a number's sign bit or distinguish a floating point number's exponent from its significand. Unlike a logical shift, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.
Приложения
Циклические коды – это разновидность блочного кода, обладающая свойством, что циклическая перестановка кодового слова всегда дает другое кодовое слово. Это обуславливает следующее общее определение: для строки s над алфавитом Σ обозначим shift(s) множество всех циклических сдвигов строки s, а для множества L строк обозначим shift(L) множество всех циклических сдвигов строк из L. Если L является циклическим кодом, то shift(L) ⊆ L; это необходимое условие для того, чтобы L был циклическим языком. Операция shift(L) изучалась в теории формальных языков. Например, если L – контекстно-свободный язык, то shift(L) также является контекстно-свободным языком. Кроме того, если L описывается регулярным выражением длины n, существует регулярное выражение длины O(n³) для описания shift(L).
and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language. The operation shift(L) has been studied in formal language theory. For instance, if L is a context free language, then shift(L) is again context free. Also, if L is described by a regular expression of length n, there is a regular expression of length O(n3) describing shift(L).