Bitreversed

Bitreversed refers to the operation or concept of reversing the order of bits in a binary representation of a number, typically within a fixed width. In practice this means taking the most significant bit of the width as the least significant, and so on, so that the bit sequence is read backward. For example, with a 3-bit width, the number 3 (binary 011) becomes 6 (binary 110) after bit reversal.

Bit reversal is often described in terms of a bit-reversal permutation, which maps each index i in the range 0 to N−1 (where N is a power of two) to the index whose binary representation is the reverse of i’s lowest log2(N) bits. This permutation is an involution: its own inverse. It is a fundamental step in several fast algorithms, most notably in the Cooley–Tukey FFT, where data are reordered into bit-reversed order to enable in-place butterfly computations.

In hardware and software, bit reversal is typically defined for a fixed word width. If N is not a power of two, the standard bit-reversal scheme is not directly applicable. Reordering can be achieved by padding or by using a generalized scheme, but most common FFT implementations assume a power-of-two length.

Computationally, several methods exist to obtain bit-reversed indices. A straightforward approach reverses bits with a loop; faster methods use lookup tables for chunks of bits, or iterative bit-twiddling that builds the reversed index in O(1) amortized time per element for a given size. In many libraries, a precomputed bit-reversed permutation or in-place swapping based on bit-reversed indices is used to minimize extra memory.

See also: Fast Fourier Transform, bitwise operations, permutations, in-place algorithms.