最近在复习FT（Fourier Transform）相关的知识，当然是要好好复习一下FFT（Fast Fourier Transform）算法啦。FFT这个伟大的算法是JW Cooley & JW Tukey在1965年提出的。 他们的论文“机器计算Fourier series的一种算法”发表在<<Mathematics of computation>> ，成为DSP发展史上的里程碑。关于FT和FFT算法相关的理论资料是很容易找到的，这里就不在复述啦。这里我想提一提“码位倒置”算法。码为倒置算法作为FFT算法的一部分，它的出现为FFT这个本来就很巧妙的算法更添一份神奇，是的冥冥之中码为倒置算法就应该出现在FFT中，这或许就是所谓的真理！

   先简单的描述一下码位倒置算法：

   尽管有很多高效简单的码位倒置算法，但它们理解起来都比较困难，针对这种情况，提出一种“循环移位”的码为倒置算法，该算法直观容易理解，而且也同样高效。算法代码如下：

   /*void bitreverse(int a[], int N)

     a[]为要改变位置的数字，N为数组a的长度，N = 2^L

   */

   void bitreverse(int a[], int N){

       //计算数组长度N的二进制站位数，即L，保存到bitsn中

       int n = N-1;

       int bitsn = 0;

       while(n != 0){

           n = n>>1;

           bitsn++;

       }

       //码位倒置，最多交换N/2次

       for(int i = 0; i < N/2; i++{

           int num = bitsn;  /*循环位移次数，bitsn次

           int pos = i;   /*当前待交换位置*/

           int des = 0;   /*目的交换位置*/

           //循环移位

           while(num > 0){

               int temp = pos;

               pos = pos>>1; /*当前待交换位置向右移出一位*/

               des = des<<1; /*目的位置左移一位，虚以待位*/

               des += temp - (pos<<1); /*将pos移出的位加到pos上*/

               num--;

           }

           //如果des和i相等则交换

           if(des != i){

               int t = a[i];

               a[i] = a[des];

               a[des] = t;

           }

       }      

   }

下面是另一种方法的流程图：