c++实现的基-2迭代cooley-tukey fft支持复数输入、自然序输出，含位逆序重排与蝶形运算，要求长度为2的幂，使用std::complex，无外部依赖，可直接编译运行。
用 C++ 实现一个高效、可读、实用的快速傅里叶变换（FFT），核心是采用 基-2 递归/迭代 Cooley-Tukey 算法，支持复数输入，输出为标准频域复数数组（按自然序，非位逆序）。下面给出一个轻量、无外部依赖、可直接编译运行的完整实现。
基础准备：使用 std::complex 和标准库
无需第三方库，仅需：
-
#include <complex></complex>和#include <vector></vector> - 使用
std::complex<double></double>表示复数 - 输入长度必须是 2 的整数次幂（自动补零或报错提示）
迭代版 FFT（推荐：避免递归开销，内存友好）
迭代实现更稳定、无栈溢出风险，适合实时信号处理。关键点是位逆序重排 + 蝶形运算分层计算：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
<p>using Complex = std::complex<double>
using VecC = std::vector<Complex></p><p>// 将 n 转换为 bit-reversed 数（bit width = log2(size)）
int bitReverse(int n, int bits) {
int rev = 0;
for (int i = 0; i < bits; ++i) {
rev |= ((n >> i) & 1) << (bits - 1 - i);
}
return rev;
}</p><p>// 基-2 迭代 FFT（in-place，升序输出）
void fft(VecC& x) {
int N = x.size();
if (N <= 1) return;</p><pre class='brush:php;toolbar:false;'>// 检查是否为 2 的幂
if ((N & (N - 1)) != 0) {
throw std::runtime_error("FFT size must be power of 2");
}
int bits = 0;
for (int n = N; n > 1; n >>= 1) ++bits;
// 位逆序重排
for (int i = 0; i < N; ++i) {
int j = bitReverse(i, bits);
if (j > i) std::swap(x[i], x[j]);
}
// 蝶形运算：按级数（m = 1,2,4,...,N/2）
for (int m = 1; m < N; m *= 2) {
double theta = M_PI / m; // π/m
Complex w_m = Complex(cos(theta), -sin(theta)); // 主根 ωₘ
for (int k = 0; k < N; k += 2 * m) {
Complex w = 1.0;
for (int j = 0; j < m; ++j) {
Complex t = w * x[k + j + m];
Complex u = x[k + j];
x[k + j] = u + t;
x[k + j + m] = u - t;
w *= w_m;
}
}
}}
使用示例：生成正弦信号并分析频谱
验证 FFT 正确性，比如对 64 点含 8Hz 正弦波（采样率 64Hz）做变换：
立即学习“C++免费学习笔记（深入）”；
int main() {
const int N = 64;
VecC signal(N);
<pre class='brush:php;toolbar:false;'>// 生成 8Hz 正弦（采样率 fs = 64Hz → 一个周期 8 点 → 频点索引 = 8）
double fs = 64.0;
for (int i = 0; i < N; ++i) {
double t = i / fs;
signal[i] = std::sin(2 * M_PI * 8 * t);
}
fft(signal);
// 输出前 12 个幅度谱（|X[k]|）
std::cout << "Magnitude spectrum (first 12 bins):\n";
for (int k = 0; k < 12; ++k) {
double mag = std::abs(signal[k]);
std::cout << "bin[" << k << "] = " << mag << "\n";
}
// 应看到 bin[8] 和 bin[56]（共轭对）幅值显著（≈32）
return 0;}
补充说明与优化建议
- 逆变换 IFFT：只需对 FFT 结果取共轭 → 调用 fft → 再取共轭并除以 N
- 实数 FFT 优化：若输入纯实数，可用 packed 格式（如将两个实序列合进一个复序列）提升 2 倍效率
-
精度注意：使用
double复数，避免float在长序列下累积误差 - 生产环境：高频/大数据推荐用 FFTW 或 Intel IPP；教学/嵌入式场景此实现足够清晰可控
基本上就这些 —— 代码简洁、逻辑清晰、可直接集成到信号采集、滤波器设计或频谱分析模块中。需要支持任意长度（Bluestein 算法）或 SIMD 加速时，再在此基础上扩展即可。
