基二乘FFT，C语言注释

下面是基于C语言的基2乘FFT算法的注释说明：

void fft(double *x, double *y, int n) {
    int i, j, k;
    double c, s, t1, t2;

    // Bit-reverse the input array x
    bit_reverse(x, y, n);

    // Perform the FFT
    for (k = 2; k <= n; k *= 2) {
        for (j = 0; j < k / 2; j++) {
            c = cos(-2 * PI * j / k);
            s = sin(-2 * PI * j / k);
            for (i = j; i < n; i += k) {
                t1 = c * x[i + k / 2] - s * y[i + k / 2];
                t2 = s * x[i + k / 2] + c * y[i + k / 2];
                x[i + k / 2] = x[i] - t1;
                y[i + k / 2] = y[i] - t2;
                x[i] += t1;
                y[i] += t2;
            }
        }
    }
}

void bit_reverse(double *x, double *y, int n) {
    int i, j, k;
    double t;

    j = 0;
    for (i = 0; i < n; i++) {
        if (j > i) {
            t = x[j];
            x[j] = x[i];
            x[i] = t;
            t = y[j];
            y[j] = y[i];
            y[i] = t;
        }
        k = n / 2;
        while (k <= j) {
            j -= k;
            k /= 2;
        }
        j += k;
    }
}

注释说明：

- `fft`函数为基2乘FFT算法的主要实现部分，参数`x`和`y`是输入输出数组，`n`是数组长度。
- `bit_reverse`函数用于将输入数组按位反转，以便在FFT计算中使用。