Bit Reversal Sorting

An Efficient Bit-Reversal Sorting Algorithm for the Fast Fourier Transform

January 16, 2005

While learning about the FFT, I invented this algorithm. To the best of my knowledge, it is both mostly unique (although similar in many ways to Cooley's method) and extremely efficient (O(n) on any CPU that has a bit-scan instruction, O(n log n) with a very small constant factor for those that have to emulate it).

The overall structure of the algorithm is similar to the other algorithms of this class. Two indexes are kept into the array to be reversed, which are maintained as bit-reverses of each other. Whenever the first is strictly smaller than the second, the two are swapped.

The innovative feature of this algorithm is that, rather than keeping one incrementing index and it's bit-reverse, the index is kept in Grey Code. Grey Code is very rarely used in software. It has the unique feature that only one bit changes at a time. With some clever use of a bit-scan instruction, which exists on most modern general-purpose CPU's, Grey Code can be generated simply. Specifically, scanning a standard count sequence to determine the least-significant bit position will yield the index of the bit to be inverted in the Grey Code sequence. Of course, subtract the index from the total number of bits and you can just as easily generate bit-reversed Grey Code, in constant time per step. Herein lies the efficiency of the algorithm.

A simple sample implementation follows. bsr and bsf represent bit-scan instructions (reverse and forward, like the x86 BSR and BSF instructions).

void reversey(int* b, int l) {
        int i,jp,jn,k,s;
        int t;
        jp=0; jn=0;

        s=bsr(l)-1;
        for(i=1; i<l; i++) {
            k=bsf(i);
            jp^=(1<<k);
            jn^=(1<<(s-k));
            if(jp<jn) {
                t=b[jp]; b[jp]=b[jn]; b[jn]=t;
            }
        }
}