Circular shift

From Wikipedia, the free encyclopedia

In combinatorial mathematics, a circular shift is a permutation of the entries in a tuple where the last element becomes the first element and all the other elements are shifted, or where the first element becomes the last element and all the other are shifted. Equivalently, a circular shift is a permutation with only one cycle.

For example, the circular shifts of the triple (a, b, c) are :

• (a, b, c) (identity);
• (c, a, b);
• (b, c, a).

The number of circular shifts of a set of size n is (n − 1)!. In terms of a cyclic order, this is a transition to one of two linear orders giving the same cyclic ordering.

In computer science, a circular shift 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.

Circular shifts are used often in cryptography as part of the permutation of bit sequences.

[edit] Example

If the bit sequence 0110 1111 1010 0011 were subjected to a circular shift of four bit positions to the left, the resulting bit sequence would be 1111 1010 0011 0110

Note that the leftmost quartet of bits, 0110, was moved to the rightmost four bit positions.