Cyclic shifts by reversal

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}
\]

A Contribution to the History of the Evolution of Thought

Excerpts from
PSYCHOLOGY OF THE UNCONSCIOUS: A Study of the Transformations and Symbolisms of the Libido. A Contribution to the History of the Evolution of Thought.

There is, of course, much more where that came from.