Circular shift

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Circular shift" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

Matrices of 8-element circular shifts to the left and right

In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either

${\displaystyle \sigma (i)\equiv (i+1)}$ modulo n, for all entries i = 1, ..., n

or

${\displaystyle \sigma (i)\equiv (i-1)}$ modulo n, for all entries i = 1, ..., n.

The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple.

For example, repeatedly applying circular shifts to the four-tuple (a, b, c, d) successively gives

• (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 ${\displaystyle {\frac {n}{k}}}$, 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.