检查 2^n 数的快速算法

引言

一些信号处理应用，例如快速傅里叶变换 (FFT)，需要采样数据输入的长度等于 2^n（其中 n 为整数，n=1,2,3,...），并且需要快速测试这个数字。尤其是在 DSP 卡（如 TMS320C6xxx DSP）上运行的实时应用中，必须在很短的时间内完成此测试。这里提供一个优化的代码片段来实现此目的。

源代码

以下函数如果数字 x 的形式为 2^n，则返回 TRUE

bool CheckInputToFFT(int x)
{
    return (!(x & (x-1)));
}

就是这样，这意味着每个数字 (2,4,8,16,...2^n) 与前一个数字进行按位与运算时，结果都为零！