Circular shift

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

σ

(

i

)

≡

(

i

+

1

)

{\displaystyle \sigma (i)\equiv (i+1)}

modulo n, for all entries i = 1, ..., n

or

σ

(

i

)

≡

(

i

−

1

)

{\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

n

k

{\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.