## 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.