Bit-reversal permutation

In applied mathematics, a bit-reversal permutation is a permutation of a sequence of ${\displaystyle n}$ items, where ${\displaystyle n=2^{k}}$ is a power of two. It is defined by indexing the elements of the sequence by the numbers from ${\displaystyle 0}$ to ${\displaystyle n-1}$, representing each of these numbers by its binary representation (padded to have length exactly ${\displaystyle k}$), and mapping each item to the item whose representation has the same bits in the reversed order.

Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an involution.

This permutation can be applied to any sequence in linear time while performing only simple index calculations. It has applications in the generation of low-discrepancy sequences and in the evaluation of fast Fourier transforms.