fft算法c语言实现 代码注释

以下是一个使用C语言实现FFT算法的代码示例，并附有注释说明：

#include <stdio.h>
#include <math.h>

// 定义复数结构体
typedef struct {
    double real;
    double imag;
} Complex;

// 交换两个复数
void swap(Complex* a, Complex* b) {
    Complex temp = *a;
    *a = *b;
    *b = temp;
}

// 计算以2为底的对数
int log2(int n) {
    int k = 0;
    while (n >>= 1) {
        k++;
    }
    return k;
}

// 基-2蝶形运算
void butterfly(Complex* a, int n) {
    // 按位反转
    int j = 0;
    for (int i = 1; i < n - 1; i++) {
        for (int k = n >> 1; k > (j ^= k); k >>= 1);
        if (i < j) {
            swap(&a[i], &a[j]);
        }
    }

    // 蝶形运算
    for (int m = 2; m <= n; m <<= 1) {
        Complex wm = { cos(-2 * M_PI / m), sin(-2 * M_PI / m) };
        for (int k = 0; k < n; k += m) {
            Complex w = { 1, 0 };
            for (int j = 0; j < m / 2; j++) {
                Complex t = { w.real * a[k + j + m / 2].real - w.imag * a[k + j + m / 2].imag, w.real * a[k + j + m / 2].imag + w.imag * a[k + j + m / 2].real };
                Complex u = a[k + j];
                a[k + j].real += t.real;
                a[k + j].imag += t.imag;
                u.real -= t.real;
                u.imag -= t.imag;
                a[k + j + m / 2] = u;
                Complex temp = { w.real * wm.real - w.imag * wm.imag, w.real * wm.imag + w.imag * wm.real };
                w = temp;
            }
        }
    }
}

// 快速傅里叶变换
void fft(Complex* x, int n) {
    // 检查n是否为2的幂次方
    int k = log2(n);
    if (1 << k != n) {
        printf("输入长度不是2的幂次方");
        return;
    }

    // 进行蝶形运算
    butterfly(x, n);
}

int main() {
    // 输入序列长度
    int n;
    printf("输入序列的长度：");
    scanf("%d", &n);

    // 创建复数数组
    Complex x[n];
    
    // 输入序列的实部和虚部
    for (int i = 0; i < n; i++) {
        printf("输入第%d个元素的实部和虚部：", i + 1);
        scanf("%lf%lf", &x[i].real, &x[i].imag);
    }

    // 调用快速傅里叶变换
    fft(x, n);

    // 输出变换结果
    printf("FFT变换结果：\n");
    for (int i = 0; i < n; i++) {
        printf("X[%d] = %.4f + %.4fi\n", i, x[i].real, x[i].imag);
    }

    return 0;
}