Circular shift

A circular shift is an operation on an ordered list (or '' N '' - uplet), consisting in making pass the last element at the beginning and shifting all the others; or contrary, to make pass the first element at the end, and to shift the others. This operation can be repeated in a recursive way .

It is about a particular case of Permutation, to distinguish from the circular Shift to which he is related.

For example, if one takes the list ( has , B , C ) - it is a Triplet -, then its successive circular shifts are:

( has , B , C );
( C , has , B );
( B , C , has ).

In a general way, if there is a N - uplet

( has ₁, has ₂,…, a_n )

then the circular shifts are obtained by applying the recursive algorithm according to:

first shift

has ^{1₁ = a_n}

for 1 < I < N , has ^{1_{I +1} = a_i}

J E shift ( J < N ):

has ^{J ₁ = has ^{J -1}_N}

for 1 < I < N , has ^{J _{I +1} = has ^{J -1}_I}

Parity

A circular shift is

a even Permutation if the number of elements is odd;
a odd Permutation if the number of elements is even.

This can be shown by recurrence on the number of elements:

for a doublet, the circular shift is a Transposition ( has , B ) → ( B , has ), it is thus an odd permutation;
for a N - uplet, the circular shift is obtained by permuting the first and the last element, then by applying a circular shift to the elements of row 2 to N in the new list (thus the elements has ₂, has ₃,…, has _{N -2}, has _{N -1}, has ₁)
$(a_1, a_2,…, a_ {n-1}, a_n) \ rightarrow (a_n,)$
the circular shift of N elements is thus the product ofa transposition with the circular shift of order N -1, there is thus a change of parity between N -1 and N .

Use in data processing

In Data-processing, the circular shift shifts all the bits of the operand considered. When the operand is a whole of bytes representing a number, this operator does not preserve the sign number nor the Mantisse and the exhibitor. Contrary to the shift registers, the vacant places left by the shift are not left empty but are filled by the bits pushed out of the operand.

The circular shift is often used in Cryptographie

; Example

If the sequence of bits 0110 1111 1010 0011 is subjected to a circular shift of four bits towards the left, the result is 1111 1010 0011 0110

Note that the four-bit byte on the left, 0110, become the four-bit byte on the right.

See too

Random links: