Bit-Reversal Permutation

A bit-reversal permutation rearranges a sequence of n = 2^k items by reversing the binary representation of each item index. Each index from 0 to n-1 is written out in binary using exactly k bits, and the item at that index is mapped to the item whose index has the same bits in reverse order; applying the permutation twice returns the sequence to its original order, since the operation is its own inverse. Bit reversal is most important in radix-2 Cooley-Tukey fast Fourier transform algorithms, where the recursive, in-place stages of the computation imply a bit reversal of the inputs or outputs. It is also used in generating low-discrepancy sequences and in establishing computational lower bounds for data structures such as binary search trees. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/