Bit-reversal permutation

In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n = 2 is a power of two. It is defined by indexing the elements of the sequence by the numbers from 0 to n − 1 and then reversing the binary representations of each of these numbers (padded so that each of these binary numbers has length exactly k). Each item is then mapped to the new position given by this reversed value. The bit reversal permutation is an involution, so repeating the same permutation twice returns to the original ordering on the items.