/******************************************************************** 
* bit_reversal.c - Arrange input samples in bit-reverse order for FFT
*                    the index j is the bit reverse of i                 
*
********************************************************************/

#include "def_complex.h"	/* floating-point header file      */

void bit_reversal(complex *x, unsigned int M)
{
  unsigned int i,j,k;
  unsigned int N = 1<<M;	/* no. of FFT point N = 2^M        */
  unsigned int N2 = N>>1;	/* N/2                             */
  complex temp;			/* complex temporary storage       */
  for (j=0,i=1;i<N-1; i++){
    k = N2;
    while(k<=j){
      j-=k;
      k>>=1;
    }
    j += k;
    if (i < j){	         /* swapping samples in bit-reversal order */
      temp = x[j];
      x[j]=x[i];
      x[i]=temp;
    }
  }
}