Bit reversal � hierarchical memory � Fast Fourier Transform c�Copyright Hewlett�Packard Company 1993

Many versions of the Fast Fourier Trans� form require a reordering of either the in� put or the output data that corresponds to reversing the order of the bits in the ar� ray index. There has been a surprisingly large number of papers on this subject in the recent literature. This paper collects 30 methods for bit reversing an array. Each method was recoded into a uniform style in Fortran and its performance measured on several di�erent machines � each with a di�erent memory system. This paper includes a de� scription of how the memories of the ma� chines operate to motivate two new algo� rithms that perform substantially better than the others. Index terms � Fast Fourier Transform � bit reversal � cache memor