C语言编程系列006——将一个正整数圆整为2的n次方的方法

问题提出

在数字信号处理领域，常遇到需要将一个正整数向上圆整为2的n次方的数据的情况，如对采集到的时域信号做频谱分析时，常要求数据点数必须满足为2的n次方，满足此种情况才可用傅里叶变换的基2快速算法，以达到较好的运算速度。换句话说，数据点数必须圆整为形如128、512、1024、4096等类型的数字。

那么，在C/C++语言中，怎样快速实现这个功能呢？假定给一个正整数x，写一个函数numTo2N，得到将其向上圆整为2的n次方的值y，下面给出几种常用方法的C/C++语言代码实现。

方法1

思路：最直接的思维方式，在while循环里将正整数x始终除以2，直到x除以2的值小于2，统计循环的次数i，若最后x除以2的值大于1，则循环次数i=i+1，返回2的i次方，即是y的值。实现代码如下：

方法2

思路：同方法1类似，给一个初始值i=1，同样在while循环里将正整数x右移1位（相当于除以2，只是舍弃了小数部分），直到x右移1位的值为0，同时，将i左移1位（相当于乘以2），最后，判断i的值，若是小于原始的x值，则返回i再左移1位的值，否则返回i的值，即是y的值。实现代码如下：

方法3

思路：将给定的数x，表示为2的次方的形式，求解次方的值，将次方向上取整为n值，返回2的n次方的值，即是要求的y值，数学推导如下：

实现代码如下：

代码测试例子

调用上面3个函数，测试代码如下：

运行结果如下：

结论

上面3种方法都可以实现我们想要的结果，其中，第1种最直观，第2种采用移位运算，运行速度最快，第3种涉及到对数的运算，运行速度最慢。

另外，在这个题目的基础上，可以进一步思考另一个问题，怎样快速判断一个数是否为2的n次方？

实际上很简单，如果一个数是2的n次方的话，二进制表示最高位一定是1，其它位是0，如对于数值x=16，其二进制表示为“10000”，则x-1=15，其二进制表示为“01111”，所以x与x-1位与运算为0，而对于不是2的n次方表示的数值，则不满足这个特点，根据这个思路，可写下面的函数进行判断一个数是否为2的n次方：

欢迎加关注，共同交流。