Bit-reversal permutation

A bit-reversal permuation is a permutation of a sequence with n=2^m (a power of two) elements, defined by reversing the binary digits of the index of each element. A generalization to arbitrary composite sizes is a mixed-radix digit reversal (in which the elements of the sequence are index by a number expressed in a mixed radix, whose digits are reversed by the permutation).

Bit reversal is most important for the radix-2 Cooley–Tukey FFT algorithm, where the recursive stages of the algorithm, operating in-place, imply a bit reversal of the inputs of outputs. Similarly, mixed-radix digit reversals arise in mixed-radix Cooley–Tukey FFTs. Mainly because of the importance of fast Fourier transform (FFT) algorithms, numerous efficient O(n) in-place algorithms for bit reversal and digit reversal permutations have been devised.