c - FFT重新排序阶段

我有一些代码给你们。
这是快速傅里叶变换分裂算法的第一步。
算法应该做的是对数组重新排序，这样输入端的每个元素都将在输出端的“二进制镜像”位置被替换。
例如，元素X[4]将位于位置X[1]，因为100的镜像表示是001。
直到这里，一切都清楚了但是，执行这种重新排序的算法不是至少我很难理解。
第二个，内环做什么？

// N is the length of the array
// p is the number of bits needed to represent the index

for(int n=0; n<N; n++) {

   int j=0;
   int m=n;
   for(int i=0; i<p; i++) {
     j = 2∗j + m%2; m = m/2;
   }

   if ( j>n) {
     complex<double> h;
     h = X[j];
     X[j] = X[n];
     X[n] = h;
   }

}

最佳答案

把整数看作是一个位序列。
j = 2j这会弹出左边的位，并将0推到右边
m % 2这将获得正确的位
m = m / 2弹出右边的位并在左边推送最左边的位的副本
j + x将j的最右边的位设置为x，假设该位当前为零，x为0或1
所以所有这些都是从m右边弹出一些位，然后把它们推到j右边。

关于c - FFT重新排序阶段，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29780329/