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