绝大多数场景下，别手写fft；应使用fftw、intel mkl等高度优化库，仅教学或极受限嵌入式环境才考虑手写。
FFT 在 C++ 中必须手写还是用库？
绝大多数场景下，别手写 FFT。标准库不提供，但 FFTW、Intel MKL、armadillo（底层调 FFTW）等已高度优化，尤其对大小非 2 的幂、多维、实数输入等有成熟处理。手写易出错，且很难跑赢 FFTW 的汇编级优化和 CPU 指令特化（如 AVX-512 复数乘法流水）。
除非你满足以下全部条件：教学演示、嵌入式资源极受限（无浮点协处理器 + 内存 fftw_plan_dft_1d。
手写基 2 递归 FFT 的核心陷阱
递归实现看似简洁，但实际部署时极易踩坑：
-
std::vector频繁拷贝导致 O(N log N) 额外内存与时间开销，应传引用 + 用预分配缓存 - 未对齐的复数数组（如
std::complex<double></double>在某些 ABI 下非 16 字节对齐）会让 SIMD 加速失效 - 忽略
bit-reversal索引计算的边界：长度为N=2^k时，索引i的反转需用k位，而非全 int 位宽；常见错误是用__builtin_bitreverse32(i)直接截断 - 蝶形运算中
W_N^k = exp(-2πi k / N)的相位精度累积误差：当N > 2^16时，用cos/sin查表或递推比直接调std::exp更稳
一个最小可行递归版本（仅示意逻辑，非生产用）：
立即学习“C++免费学习笔记（深入）”；
void fft_recursive(std::vector<std::complex<double>>& x) {
int n = x.size();
if (n <= 1) return;
std::vector<std::complex<double>> even(n/2), odd(n/2);
for (int i = 0; i < n/2; ++i) {
even[i] = x[2*i];
odd[i] = x[2*i+1];
}
fft_recursive(even);
fft_recursive(odd);
for (int k = 0; k < n/2; ++k) {
std::complex<double> t = std::polar(1.0, -2 * M_PI * k / n) * odd[k];
x[k] = even[k] + t;
x[k+n/2] = even[k] - t;
}
}
迭代版 FFT 的蝶形索引怎么算才不崩？
迭代版避免递归开销，但 bit-reversal permutation 是关键。错误做法：对每个 i 单独调用 std::bitset 反转再转回整数——O(N log N) 时间爆炸。
正确做法：用 in-place 位翻转算法，时间复杂度 O(N)：
- 维护一个
rev数组，rev[i]表示i的log2(N)位反转值 - 初始化
rev[0] = 0，对i从 1 到N-1，用rev[i] = (rev[i>>1]>>1) | ((i&1) 递推（<code>bits = log2(N)） - 蝶形循环中，只处理
i 的对，避免重复交换
注意：std::polar(1.0, theta) 构造旋转因子效率低，应预先计算并存入 std::vector<:complex>> w</:complex>，且用 cos(theta) 和 sin(theta) 分离存储可减少虚部运算开销。
频域转换后幅度谱为什么总在 0Hz 处炸？
这不是 FFT 错，而是输入信号没去直流偏移。若原始数据是 short 音频采样（范围 [-32768, 32767]），直接转 double 后做 FFT，其均值非零 → 0Hz bin 能量远超其余频率。
解决方法只有两个：
- 时域预处理：对输入向量
x减去均值std::accumulate(x.begin(), x.end(), 0.0) / x.size() - 或改用实数 FFT（
fftw_plan_dft_r2c_1d），它隐含要求输入为实数，且输出共轭对称，但依然要先去均值
另外，幅度谱需用 abs(x[k]) 而非 norm(x[k])（后者是模的平方），且通常要加窗（如 hann 窗）抑制频谱泄漏——这步在 FFT 前做，不是 FFT 本身的责任。
真正难的从来不是蝶形公式，而是对齐、缓存局部性、数值稳定性、以及理解「FFT 输出的是什么」——比如，fftw 默认不归一化，逆变换需手动除以 N，这点连很多文档都写得含糊。
