α(x) = |x + 1|N
Informally, the destination label is the numerical value of the source label plus one, modulo N. When represented as a bipartite graph the shift permutation looks like that shown in the figure.
The inverse of the shift permutation, α-1(x), is also useful and can be observed by reading the bipartite graph for α(x) backwards. Hence
α-1(x) = |x - 1|N
The shift permutation is an arithmetic permutation, rather than a logical permutation, as the label is permuted by a numerical function as opposed to a bit-manipulation function. Permutations involving bit-manipulations, if capable of permuting any n-bit source label to an n-bit destination label, do so in a maximum of n = log2(N) applications of the permutation. However, permutations involving incremental arithmetic functions on labels may require as many as N applications of the arithmetic function. As a consequence routing functions constructed from shift permutations are not as powerful as those constructed from the exchange, shuffle and butterfly permutations unless the source and destination labels differ, on average, by less than log2N.