bit_reverse_swap

void change(Complex y[],int len)
{
    int i,j,k;
    for(i = 1, j = len/2;i < len-1;i++)
    {
        if(i < j)swap(y[i],y[j]);
        k = len/2;
        while( j >= k)
        {
            j -= k;
            k /= 2;
        }
        if(j < k)j += k;
    }
}

inline unsigned int bit_reverse(unsigned int a, int len){
    a = ((a&0x55555555U) << 1) | ((a&0xAAAAAAAAU) >> 1);
    a = ((a&0x33333333U) << 2) | ((a&0xCCCCCCCCU) >> 2);
    a = ((a&0x0F0F0F0FU) << 4) | ((a&0xF0F0F0F0U) >> 4);
    a = ((a&0x00FF00FFU) << 8) | ((a&0xFF00FF00U) >> 8);
    a = ((a&0x0000FFFFU) << 16) | ((a&0xFFFF0000U) >> 16);
    return a>>(32-len); 
}

for(int i=0;i<n;i++) r[i]=(r[i/2]>>1)|((i&1)<<(l-1));

void FFT(C* a, int n, int t){
22     bit_reverse_swap(a, n);
23     for(int i=2; i<=n; i<<=1){
24         C wi(cos(t*2*PI/i), sin(t*2*PI/i));
25         for(int j=0; j<n; j+=i){
26             C w(1);
27             for(int k=j, h=i>>1; k<j+h; k++){
28                 C t=w*a[k+h], u=a[k];
29                 a[k]=u+t;
30                 a[k+h]=u-t;
31                 w*=wi;
32             }
33         }
34     }
35     if(t==-1) rep(i, 0, n) a[i]/=n;
36 }