位反转

位反转（Bit-Reversal）是FFT中用于原地计算、节省内存的巧妙数据重排技术。在进行不断地对半拆分后，输入数据最初的自然顺序会被彻底打乱。工程师们发现，这个看似混乱的序列其实遵循着严密的位反转规律：只要把原索引的二进制数倒过来写，就能得到数据洗牌后的新位置。这种规律意味着计算机在内存中计算时，不需要开辟庞大的额外缓存区，可以直接在这个被打乱的数组内部进行原地更新（In-place Computation），极大地节省了宝贵的内存空间，并大幅提高了处理器缓存的运行效率。