最近在复习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;
}
}
}
下面是另一种方法的流程图：
