Cyclic shifts/rotates are often used in crypto; they are like normal “arithmetic” shifts (`<<`

and `>>`

) except the bits that are shifted off are added back in at the other end:

`[0 1 2 3 4]`

cyclically shifted two to the left is `[2 3 4 0 1]`

.

An array of length \(n\) can be cyclically shifted \(k\) spaces in \(\mathcal{O}(1)\) space and \(\mathcal{O}(n)\) time using three reversals, as follows: for a left shift, reverse the entire array, then reverse the first \(n-k\) elements, followed by the last \(k\) elements. For a right shift, do the reversal of the entire array after instead of before.

This works as follows: mathematically, consider an array \(A\;B\;C\) consisting of the concatenation of three sub-arrays \(A\), \(B\), and \(C\). Let \(X’\) be the reversal of \(X\).

A left shift by the length of \(A\):

\[
\begin{array}{lll}

A & B & C & \\

C’ & B’ & A’ & \text{(reverse whole array)} \\

B^{\prime\prime} & C^{\prime\prime} & A^{\prime\prime} & \text{(two separate reversals)} \\

B & C & A

\end{array}

\]

A right shift by the length of \(C\):

\[
\begin{array}{lll}

A & B & C \\

B’ & A’ & C’ \\

C^{\prime\prime} & A^{\prime\prime} & B^{\prime\prime} \\

C & A & B

\end{array}

\]