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次方:

欢迎加关注,共同交流。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180911A12H3A00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券