Gold Rader 位反转算法
Gold Rader bit reversal algorithm
我想了解这个位反转算法。我找到了很多资源，但并没有真正解释伪代码的工作原理。例如，我从http://www.briangough.com/fftalgorithms.pdf
中找到了下面的伪代码
for i = 0 ... n − 2 do
k = n/2
if i < j then
swap g(i) and g(j)
end if
while k ≤ j do
j ⇐ j − k
k ⇐ k/2
end while
j ⇐ j + k
end for
看了这个伪代码，不明白你为什么要这么做
swap g(i) and g(j)
当 if 语句为 true.
另外：while 循环有什么作用？如果有人能向我解释这个伪代码，那就太好了。
下面是网上找的c++代码
void four1(double data[], int nn, int isign)
{
int n, mmax, m, j, istep, i;
double wtemp, wr, wpr, wpi, wi, theta;
double tempr, tempi;
n = nn << 1;
j = 1;
for (i = 1; i < n; i += 2) {
if (j > i) {
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
}
m = n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
}
j += m;
}
这是我发现的执行 FFT 的源代码的完整版本
/************************************************
* FFT code from the book Numerical Recipes in C *
* Visit www.nr.com for the licence. *
************************************************/
// The following line must be defined before including math.h to correctly define M_PI
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define PI M_PI /* pi to machine precision, defined in math.h */
#define TWOPI (2.0*PI)
/*
FFT/IFFT routine. (see pages 507-508 of Numerical Recipes in C)
Inputs:
data[] : array of complex* data points of size 2*NFFT+1.
data[0] is unused,
* the n'th complex number x(n), for 0 <= n <= length(x)-1, is stored as:
data[2*n+1] = real(x(n))
data[2*n+2] = imag(x(n))
if length(Nx) < NFFT, the remainder of the array must be padded with zeros
nn : FFT order NFFT. This MUST be a power of 2 and >= length(x).
isign: if set to 1,
computes the forward FFT
if set to -1,
computes Inverse FFT - in this case the output values have
to be manually normalized by multiplying with 1/NFFT.
Outputs:
data[] : The FFT or IFFT results are stored in data, overwriting the input.
*/
void four1(double data[], int nn, int isign)
{
int n, mmax, m, j, istep, i;
double wtemp, wr, wpr, wpi, wi, theta;
double tempr, tempi;
n = nn << 1;
j = 1;
for (i = 1; i < n; i += 2) {
if (j > i) {
//swap the real part
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
//swap the complex part
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
}
m = n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
}
j += m;
}
mmax = 2;
while (n > mmax) {
istep = 2*mmax;
theta = TWOPI/(isign*mmax);
wtemp = sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi = sin(theta);
wr = 1.0;
wi = 0.0;
for (m = 1; m < mmax; m += 2) {
for (i = m; i <= n; i += istep) {
j =i + mmax;
tempr = wr*data[j] - wi*data[j+1];
tempi = wr*data[j+1] + wi*data[j];
data[j] = data[i] - tempr;
data[j+1] = data[i+1] - tempi;
data[i] += tempr;
data[i+1] += tempi;
}
wr = (wtemp = wr)*wpr - wi*wpi + wr;
wi = wi*wpr + wtemp*wpi + wi;
}
mmax = istep;
}
}
/********************************************************
* The following is a test routine that generates a ramp *
* with 10 elements, finds their FFT, and then finds the *
* original sequence using inverse FFT *
********************************************************/
int main(int argc, char * argv[])
{
int i;
int Nx;
int NFFT;
double *x;
double *X;
/* generate a ramp with 10 numbers */
Nx = 10;
printf("Nx = %d\n", Nx);
x = (double *) malloc(Nx * sizeof(double));
for(i=0; i<Nx; i++)
{
x[i] = i;
}
/* calculate NFFT as the next higher power of 2 >= Nx */
NFFT = (int)pow(2.0, ceil(log((double)Nx)/log(2.0)));
printf("NFFT = %d\n", NFFT);
/* allocate memory for NFFT complex numbers (note the +1) */
X = (double *) malloc((2*NFFT+1) * sizeof(double));
/* Storing x(n) in a complex array to make it work with four1.
This is needed even though x(n) is purely real in this case. */
for(i=0; i<Nx; i++)
{
X[2*i+1] = x[i];
X[2*i+2] = 0.0;
}
/* pad the remainder of the array with zeros (0 + 0 j) */
for(i=Nx; i<NFFT; i++)
{
X[2*i+1] = 0.0;
X[2*i+2] = 0.0;
}
printf("\nInput complex sequence (padded to next highest power of 2):\n");
for(i=0; i<NFFT; i++)
{
printf("x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
/* calculate FFT */
four1(X, NFFT, 1);
printf("\nFFT:\n");
for(i=0; i<NFFT; i++)
{
printf("X[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
/* calculate IFFT */
four1(X, NFFT, -1);
/* normalize the IFFT */
for(i=0; i<NFFT; i++)
{
X[2*i+1] /= NFFT;
X[2*i+2] /= NFFT;
}
printf("\nComplex sequence reconstructed by IFFT:\n");
for(i=0; i<NFFT; i++)
{
printf("x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
getchar();
}
/*
Nx = 10
NFFT = 16
Input complex sequence (padded to next highest power of 2):
x[0] = (0.00 + j 0.00)
x[1] = (1.00 + j 0.00)
x[2] = (2.00 + j 0.00)
x[3] = (3.00 + j 0.00)
x[4] = (4.00 + j 0.00)
x[5] = (5.00 + j 0.00)
x[6] = (6.00 + j 0.00)
x[7] = (7.00 + j 0.00)
x[8] = (8.00 + j 0.00)
x[9] = (9.00 + j 0.00)
x[10] = (0.00 + j 0.00)
x[11] = (0.00 + j 0.00)
x[12] = (0.00 + j 0.00)
x[13] = (0.00 + j 0.00)
x[14] = (0.00 + j 0.00)
x[15] = (0.00 + j 0.00)
FFT:
X[0] = (45.00 + j 0.00)
X[1] = (-25.45 + j 16.67)
X[2] = (10.36 + j -3.29)
X[3] = (-9.06 + j -2.33)
X[4] = (4.00 + j 5.00)
X[5] = (-1.28 + j -5.64)
X[6] = (-2.36 + j 4.71)
X[7] = (3.80 + j -2.65)
X[8] = (-5.00 + j 0.00)
X[9] = (3.80 + j 2.65)
X[10] = (-2.36 + j -4.71)
X[11] = (-1.28 + j 5.64)
X[12] = (4.00 + j -5.00)
X[13] = (-9.06 + j 2.33)
X[14] = (10.36 + j 3.29)
X[15] = (-25.45 + j -16.67)
Complex sequence reconstructed by IFFT:
x[0] = (0.00 + j -0.00)
x[1] = (1.00 + j -0.00)
x[2] = (2.00 + j 0.00)
x[3] = (3.00 + j -0.00)
x[4] = (4.00 + j -0.00)
x[5] = (5.00 + j 0.00)
x[6] = (6.00 + j -0.00)
x[7] = (7.00 + j -0.00)
x[8] = (8.00 + j 0.00)
x[9] = (9.00 + j 0.00)
x[10] = (0.00 + j -0.00)
x[11] = (0.00 + j -0.00)
x[12] = (0.00 + j 0.00)
x[13] = (-0.00 + j -0.00)
x[14] = (0.00 + j 0.00)
x[15] = (0.00 + j 0.00)
*/
位反转算法通过反转每个项目的二进制地址来创建数据集的排列；所以例如在 16 项集合中地址：
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
将更改为：
1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
然后相应的项目被移动到他们的新地址。
或十进制：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
变成
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
伪代码中 while 循环的作用是将变量 j 设置为该序列。 （顺便说一句，j的初始值应该是0）。
你会看到序列是这样组成的：
0
0 1
0 2 1 3
0 4 2 6 1 5 3 7
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
每个序列都是通过将前一个版本乘以 2，然后重复添加 1 来制作的。或者换一种方式看：通过重复前面的序列，与值 + n/2 交错（这更准确地描述了算法中发生的事情）。
0
0 1
0 2 1 3
0 4 2 6 1 5 3 7
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
然后在 for 循环的每次迭代中交换项目 i 和 j，但前提是 i < j；否则每个项目都会被交换到它的新位置（例如，当 i = 3 和 j = 12 时），然后再返回（当 i = 12 和 j = 3 时）。
function bitReversal(data) {
var n = data.length;
var j = 0;
for (i = 0; i < n - 1; i++) {
var k = n / 2;
if (i < j) {
var temp = data[i]; data[i] = data[j]; data[j] = temp;
}
while (k <= j) {
j -= k;
k /= 2;
}
j += k;
}
return(data);
}
console.log(bitReversal([0,1]));
console.log(bitReversal([0,1,2,3]));
console.log(bitReversal([0,1,2,3,4,5,6,7]));
console.log(bitReversal([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));
console.log(bitReversal(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]));
您找到的 C++ 代码似乎使用序列的对称性以双步循环遍历它。但是它并没有产生正确的结果，所以它要么是一次失败的尝试，要么可能是为了做一些完全不同的事情而设计的。这是一个使用两步想法的版本：
function bitReversal2(data) {
var n = data.length;
var j = 0;
for (i = 0; i < n; i += 2) {
if (i < j) {
var temp = data[i]; data[i] = data[j]; data[j] = temp;
}
else {
var temp = data[n-1 - i]; data[n-1 - i] = data[n-1 - j]; data[n-1 - j] = temp;
}
var k = n / 4;
while (k <= j) {
j -= k;
k /= 2;
}
j += k;
}
return(data);
}
console.log(bitReversal2([0,1]));
console.log(bitReversal2([0,1,2,3]));
console.log(bitReversal2([0,1,2,3,4,5,6,7]));
console.log(bitReversal2([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));
console.log(bitReversal2(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]));
首先感谢大家帮忙解答我的问题。我正在和帮助我的人交谈，我想我现在理解了我的 C++ 代码。也许我的问题有点不清楚，但我想做的是使用 C++ 实现 FFT。我题中给出的C++代码只是网上找的FFT源码的前半部分。本质上，这部分 C++ 代码将输入排序为实数和虚数，将实数存储到奇数索引中，将虚数存储到偶数索引中。 (real_0, imag_0, real_1, imag_1, real_2, imag_2,.....) 索引从 1 开始，因为我们不需要交换第零个索引。
下面的交换操作是交换实数和虚数。
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
例如，我们有一个数组长度为8（nn=8），那么2*nn=16，我们将输入分为实数和虚数，并将其存储到一个16的数组中。所以第一个时间通过 C++ 代码的 for 循环，我的 j=1、i=1，它将跳过 if 和 while 语句，现在在第二个 for循环，j=9，i=3，所以 if 语句将为真，data[9]、data[3] 将被交换，data[9+1] 和 data[3+1] 将被交换交换。这是在进行位反转，因为索引 3 和 4 具有 first 输入的实数和虚数，而索引 9 和 10 具有 输入的实数和虚数第四个号。
结果，001 = 1（拳头输入）
100 = 4 (fourth input)
被交换，所以，这是使用索引进行位反转。
我还不太了解while循环，但是我从@m69那里知道，它只是一种设置序列的方式，所以它可以进行位反转。对有相同问题的人来说，我对自己问题的解释很有帮助。再次感谢大家。
我想了解这个位反转算法。我找到了很多资源，但并没有真正解释伪代码的工作原理。例如，我从http://www.briangough.com/fftalgorithms.pdf
中找到了下面的伪代码for i = 0 ... n − 2 do
k = n/2
if i < j then
swap g(i) and g(j)
end if
while k ≤ j do
j ⇐ j − k
k ⇐ k/2
end while
j ⇐ j + k
end for
看了这个伪代码，不明白你为什么要这么做
swap g(i) and g(j)
当 if 语句为 true.
另外：while 循环有什么作用？如果有人能向我解释这个伪代码，那就太好了。
下面是网上找的c++代码
void four1(double data[], int nn, int isign)
{
int n, mmax, m, j, istep, i;
double wtemp, wr, wpr, wpi, wi, theta;
double tempr, tempi;
n = nn << 1;
j = 1;
for (i = 1; i < n; i += 2) {
if (j > i) {
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
}
m = n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
}
j += m;
}
这是我发现的执行 FFT 的源代码的完整版本
/************************************************
* FFT code from the book Numerical Recipes in C *
* Visit www.nr.com for the licence. *
************************************************/
// The following line must be defined before including math.h to correctly define M_PI
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define PI M_PI /* pi to machine precision, defined in math.h */
#define TWOPI (2.0*PI)
/*
FFT/IFFT routine. (see pages 507-508 of Numerical Recipes in C)
Inputs:
data[] : array of complex* data points of size 2*NFFT+1.
data[0] is unused,
* the n'th complex number x(n), for 0 <= n <= length(x)-1, is stored as:
data[2*n+1] = real(x(n))
data[2*n+2] = imag(x(n))
if length(Nx) < NFFT, the remainder of the array must be padded with zeros
nn : FFT order NFFT. This MUST be a power of 2 and >= length(x).
isign: if set to 1,
computes the forward FFT
if set to -1,
computes Inverse FFT - in this case the output values have
to be manually normalized by multiplying with 1/NFFT.
Outputs:
data[] : The FFT or IFFT results are stored in data, overwriting the input.
*/
void four1(double data[], int nn, int isign)
{
int n, mmax, m, j, istep, i;
double wtemp, wr, wpr, wpi, wi, theta;
double tempr, tempi;
n = nn << 1;
j = 1;
for (i = 1; i < n; i += 2) {
if (j > i) {
//swap the real part
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
//swap the complex part
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
}
m = n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
}
j += m;
}
mmax = 2;
while (n > mmax) {
istep = 2*mmax;
theta = TWOPI/(isign*mmax);
wtemp = sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi = sin(theta);
wr = 1.0;
wi = 0.0;
for (m = 1; m < mmax; m += 2) {
for (i = m; i <= n; i += istep) {
j =i + mmax;
tempr = wr*data[j] - wi*data[j+1];
tempi = wr*data[j+1] + wi*data[j];
data[j] = data[i] - tempr;
data[j+1] = data[i+1] - tempi;
data[i] += tempr;
data[i+1] += tempi;
}
wr = (wtemp = wr)*wpr - wi*wpi + wr;
wi = wi*wpr + wtemp*wpi + wi;
}
mmax = istep;
}
}
/********************************************************
* The following is a test routine that generates a ramp *
* with 10 elements, finds their FFT, and then finds the *
* original sequence using inverse FFT *
********************************************************/
int main(int argc, char * argv[])
{
int i;
int Nx;
int NFFT;
double *x;
double *X;
/* generate a ramp with 10 numbers */
Nx = 10;
printf("Nx = %d\n", Nx);
x = (double *) malloc(Nx * sizeof(double));
for(i=0; i<Nx; i++)
{
x[i] = i;
}
/* calculate NFFT as the next higher power of 2 >= Nx */
NFFT = (int)pow(2.0, ceil(log((double)Nx)/log(2.0)));
printf("NFFT = %d\n", NFFT);
/* allocate memory for NFFT complex numbers (note the +1) */
X = (double *) malloc((2*NFFT+1) * sizeof(double));
/* Storing x(n) in a complex array to make it work with four1.
This is needed even though x(n) is purely real in this case. */
for(i=0; i<Nx; i++)
{
X[2*i+1] = x[i];
X[2*i+2] = 0.0;
}
/* pad the remainder of the array with zeros (0 + 0 j) */
for(i=Nx; i<NFFT; i++)
{
X[2*i+1] = 0.0;
X[2*i+2] = 0.0;
}
printf("\nInput complex sequence (padded to next highest power of 2):\n");
for(i=0; i<NFFT; i++)
{
printf("x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
/* calculate FFT */
four1(X, NFFT, 1);
printf("\nFFT:\n");
for(i=0; i<NFFT; i++)
{
printf("X[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
/* calculate IFFT */
four1(X, NFFT, -1);
/* normalize the IFFT */
for(i=0; i<NFFT; i++)
{
X[2*i+1] /= NFFT;
X[2*i+2] /= NFFT;
}
printf("\nComplex sequence reconstructed by IFFT:\n");
for(i=0; i<NFFT; i++)
{
printf("x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
}
getchar();
}
/*
Nx = 10
NFFT = 16
Input complex sequence (padded to next highest power of 2):
x[0] = (0.00 + j 0.00)
x[1] = (1.00 + j 0.00)
x[2] = (2.00 + j 0.00)
x[3] = (3.00 + j 0.00)
x[4] = (4.00 + j 0.00)
x[5] = (5.00 + j 0.00)
x[6] = (6.00 + j 0.00)
x[7] = (7.00 + j 0.00)
x[8] = (8.00 + j 0.00)
x[9] = (9.00 + j 0.00)
x[10] = (0.00 + j 0.00)
x[11] = (0.00 + j 0.00)
x[12] = (0.00 + j 0.00)
x[13] = (0.00 + j 0.00)
x[14] = (0.00 + j 0.00)
x[15] = (0.00 + j 0.00)
FFT:
X[0] = (45.00 + j 0.00)
X[1] = (-25.45 + j 16.67)
X[2] = (10.36 + j -3.29)
X[3] = (-9.06 + j -2.33)
X[4] = (4.00 + j 5.00)
X[5] = (-1.28 + j -5.64)
X[6] = (-2.36 + j 4.71)
X[7] = (3.80 + j -2.65)
X[8] = (-5.00 + j 0.00)
X[9] = (3.80 + j 2.65)
X[10] = (-2.36 + j -4.71)
X[11] = (-1.28 + j 5.64)
X[12] = (4.00 + j -5.00)
X[13] = (-9.06 + j 2.33)
X[14] = (10.36 + j 3.29)
X[15] = (-25.45 + j -16.67)
Complex sequence reconstructed by IFFT:
x[0] = (0.00 + j -0.00)
x[1] = (1.00 + j -0.00)
x[2] = (2.00 + j 0.00)
x[3] = (3.00 + j -0.00)
x[4] = (4.00 + j -0.00)
x[5] = (5.00 + j 0.00)
x[6] = (6.00 + j -0.00)
x[7] = (7.00 + j -0.00)
x[8] = (8.00 + j 0.00)
x[9] = (9.00 + j 0.00)
x[10] = (0.00 + j -0.00)
x[11] = (0.00 + j -0.00)
x[12] = (0.00 + j 0.00)
x[13] = (-0.00 + j -0.00)
x[14] = (0.00 + j 0.00)
x[15] = (0.00 + j 0.00)
*/
位反转算法通过反转每个项目的二进制地址来创建数据集的排列；所以例如在 16 项集合中地址：
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
将更改为：
1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
然后相应的项目被移动到他们的新地址。
或十进制：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
变成
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
伪代码中 while 循环的作用是将变量 j 设置为该序列。 （顺便说一句，j的初始值应该是0）。
你会看到序列是这样组成的：
0
0 1
0 2 1 3
0 4 2 6 1 5 3 7
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
每个序列都是通过将前一个版本乘以 2，然后重复添加 1 来制作的。或者换一种方式看：通过重复前面的序列，与值 + n/2 交错（这更准确地描述了算法中发生的事情）。
0
0 1
0 2 1 3
0 4 2 6 1 5 3 7
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
然后在 for 循环的每次迭代中交换项目 i 和 j，但前提是 i < j；否则每个项目都会被交换到它的新位置（例如，当 i = 3 和 j = 12 时），然后再返回（当 i = 12 和 j = 3 时）。
function bitReversal(data) {
var n = data.length;
var j = 0;
for (i = 0; i < n - 1; i++) {
var k = n / 2;
if (i < j) {
var temp = data[i]; data[i] = data[j]; data[j] = temp;
}
while (k <= j) {
j -= k;
k /= 2;
}
j += k;
}
return(data);
}
console.log(bitReversal([0,1]));
console.log(bitReversal([0,1,2,3]));
console.log(bitReversal([0,1,2,3,4,5,6,7]));
console.log(bitReversal([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));
console.log(bitReversal(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]));
您找到的 C++ 代码似乎使用序列的对称性以双步循环遍历它。但是它并没有产生正确的结果，所以它要么是一次失败的尝试，要么可能是为了做一些完全不同的事情而设计的。这是一个使用两步想法的版本：
function bitReversal2(data) {
var n = data.length;
var j = 0;
for (i = 0; i < n; i += 2) {
if (i < j) {
var temp = data[i]; data[i] = data[j]; data[j] = temp;
}
else {
var temp = data[n-1 - i]; data[n-1 - i] = data[n-1 - j]; data[n-1 - j] = temp;
}
var k = n / 4;
while (k <= j) {
j -= k;
k /= 2;
}
j += k;
}
return(data);
}
console.log(bitReversal2([0,1]));
console.log(bitReversal2([0,1,2,3]));
console.log(bitReversal2([0,1,2,3,4,5,6,7]));
console.log(bitReversal2([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));
console.log(bitReversal2(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]));
首先感谢大家帮忙解答我的问题。我正在和帮助我的人交谈，我想我现在理解了我的 C++ 代码。也许我的问题有点不清楚，但我想做的是使用 C++ 实现 FFT。我题中给出的C++代码只是网上找的FFT源码的前半部分。本质上，这部分 C++ 代码将输入排序为实数和虚数，将实数存储到奇数索引中，将虚数存储到偶数索引中。 (real_0, imag_0, real_1, imag_1, real_2, imag_2,.....) 索引从 1 开始，因为我们不需要交换第零个索引。
下面的交换操作是交换实数和虚数。
tempr = data[j]; data[j] = data[i]; data[i] = tempr;
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
例如，我们有一个数组长度为8（nn=8），那么2*nn=16，我们将输入分为实数和虚数，并将其存储到一个16的数组中。所以第一个时间通过 C++ 代码的 for 循环，我的 j=1、i=1，它将跳过 if 和 while 语句，现在在第二个 for循环，j=9，i=3，所以 if 语句将为真，data[9]、data[3] 将被交换，data[9+1] 和 data[3+1] 将被交换交换。这是在进行位反转，因为索引 3 和 4 具有 first 输入的实数和虚数，而索引 9 和 10 具有 输入的实数和虚数第四个号。
结果，001 = 1（拳头输入）
100 = 4 (fourth input)
被交换，所以，这是使用索引进行位反转。
我还不太了解while循环，但是我从@m69那里知道，它只是一种设置序列的方式，所以它可以进行位反转。对有相同问题的人来说，我对自己问题的解释很有帮助。再次感谢大家。