Bit-reversal permutation (${\mathrm{rev}}_m(j)$)

The bit-reversal permutation of $\{0,\dots ,2^m-1\}$ writes each index using exactly $m$ binary digits, reverses those digits, and interprets the result as another index. Leading zeros matter. Reversing twice restores the original index, so this permutation is an involution.

For $m=3$, the index order becomes $0,4,2,6,1,5,3,7$: for example, $3=011_2$ maps to $110_2=6$. It occurs naturally in radix-two Fast Fourier transform implementations. Repeatedly separating even from odd indices consumes the low-order bits first; traversing the resulting recursion tree reverses the order in which the index bits are read. Some implementations permute inputs, others permute outputs, and other layouts avoid an explicit reversal. The discrete Fourier transform itself is independent of this storage choice.^[ref]