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. Thus, a circular shift is given by the action of a particular permutation σ of the n positions in the tuple, for which modulo n for all i (or modulo n for the inverse operation). This permutation is a (very particular) instance of an n-cycle.

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, a, c) successively gives

• (c, a, b, a),
• (a, c, a, b),
• (b, a, c, a),
• (a, b, a, c) (the original four-tuple),

and then the sequence repeats; this four-tuple therefore has four circular shifts. However the 4-tuple (a, b, a, b) only has 2 (distinct) circular shifts. In general the number of circular shifts of an n-tuple could be any divisor of n, depending on the entries of the tuple.

In computer programming, a circular shift (or bitwise rotation) is a shift operator 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 number's exponent from its mantissa. 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.