Bitreflection

Bitreflection is the operation of reversing the order of bits in a fixed-width binary representation. For an n-bit word, it maps the bit sequence b1 b2 ... bn to bn ... b2 b1.

Notationally, if x is an n-bit integer with bits b0 through b(n-1), the bitreflection br_n(x) is defined by br_n(x) = sum_{i=0}^{n-1} b_i 2^{n-1-i}. Bitreflection is an involution: applying it twice returns the original value, and it constitutes a permutation of the 2^n possible n-bit words. The result depends on the chosen width n, so leading zeros matter in the transformation.

Example: for n = 4, x = 11, which is binary 1011, yields br_4(11) = 13, which is binary 1101.

Applications of bitreflection commonly arise in digital signal processing and algorithms that operate on binary data with fixed word sizes. It is a central component in bit-reversal permutations used to reorder data for in-place implementations of the radix-2 fast Fourier transform, where the data is accessed in reversed-bit order. Beyond FFTs, bitreflection can appear in memory addressing schemes, routing networks, and certain coding or cryptographic algorithms that rely on reversed bit mappings.

Implementation notes: a straightforward method computes br_n(x) by iterating over each bit and setting the mirrored bit in the result, giving O(n) bit operations. Optimizations include using a precomputed lookup table for small widths, or designing hardware or software bit-reversal networks that perform the reversal in fewer stages. The width n must be fixed for a consistent reversal, as changing n changes the mapping.