THE BIT REVERSAL — a dart

THE BIT REVERSAL read the bits back to front — the reindexing the FFT is built on

Reverse the bits of a number and you get its bit-reversal permutation index — 000101 becomes 101000. This is not idle: the Fast Fourier Transform leaves its outputs in exactly this scrambled order, and undoing it is a bit-reversal. The simplest form peels the low bit and shifts it onto an accumulator; the fast forms swap bit-groups in a butterfly (like the-round-up cascade in reverse). It is a small involution — reverse twice and you are home — and it is the reindexing at the seam of nearly every FFT implementation.

THE TECHNIQUE peel low bit, shift onto acc — the FFT reordering

The demo reverses the low 6 bits of 5 (000101) to get 40 (101000), peeling one bit per step onto an accumulator: live demo

HISTORY & CREDIT bit-reversal permutation · FFT reindexing

“Bit reversal is a curiosity.” — it is the exact index permutation the FFT produces and must undo; every radix-2 transform depends on it. cited

the peel · acc = (acc«1) | (n & 1); n >>= 1 — move the low bit to the high end, w times.
the involution · reverse the same width twice and you recover the original — its own inverse.
the use · radix-2 FFT (Cooley–Tukey, 1965) emits bit-reversed order; the reindex restores it.

The bits read back to front — a self-inverse permutation, and the hinge of every radix-2 FFT. resource / self-inverse

RECOMMEND FOR I-13 the bit-reversal, on the compiler

On the canonical compiler, reversing the low 6 bits of 5 (000101) yields 40 (101000):

$ i13 run tk_bitreversal.i13 # peel low bit onto acc, 6 bits RUN OK · 145 step(s) · peak stack 6 · call depth 7 n = 5 -- 000101 r = 40 -- 101000 same = 1 -- reverse of the low 6 bits

Recommend as the batch’s close — a NULL that echoes the opener. Bit reversal is, like the-xor-swap (406), a self-inverse: reverse twice and you are home, so it lives on the seal/palindrome axis THE ONE already holds — a duplicate, not a new pillar. And in its role as FFT reindexing it is again resource/permutation: the same reordering by loop, by butterfly, or by table, same result. So the batch closes as it opened: a beautiful involution that is either a seated axis (self-inverse) or a resource saving (B40). Sixteen tricks, sixteen NULLs — the strongest evidence yet that cleverness-of-mechanism is precisely what the gates exclude.