【摘要】:所以,要想判断一个数是否为2的n次方,只需要判断该数移位后的值是否与给定的数相等,实现代码如下:程序的运行结果如下:8能表示成2的n次方9不能表示成2的n次方算法性能分析:上述算法的时间复杂度为O((log2n)。因此,判断一个数是否为2的n次方可以转换为这个数对应的二进制表示中是否只有一位为1。可以利用这种方法来判断一个数是否为2的n次方。
【出自ALBB面试题】
难度系数:★★★☆☆ 被考察系数:★★★★★
分析与解答:
方法一:构造法
2的n次方可以表示为2^0,2^1,2^2,2^n,如果一个数是2的n次方,那么最直观的的想法是对1执行了移位操作(每次左移一位),即通过移位得到的值必定是2的n次方(针对n的所有取值构造出所有可能的值)。所以,要想判断一个数是否为2的n次方,只需要判断该数移位后的值是否与给定的数相等,实现代码如下:
程序的运行结果如下:
8能表示成2的n次方
9不能表示成2的n次方(www.xing528.com)
算法性能分析:
上述算法的时间复杂度为O((log2n)。
方法二:与操作法
那么是否存在效率更高的算法呢?通过对2^0,2^1,2^2,…,2^n进行分析,发现这些数字的二进制形式分别为:1,10,100,…。从二进制的表示可以看出,如果一个数是2的n次方,那么这个数对应的二进制表示中有且只有一位是1,其余位都为0。因此,判断一个数是否为2的n次方可以转换为这个数对应的二进制表示中是否只有一位为1。如果一个数的二进制表示中只有一位是1,例如num=00010000,那么num-1的二进制表示为num-1=00001111,由于num与num-1二进制表示中每一位都不相同,因此,num&(num-1)的运算结果为0。可以利用这种方法来判断一个数是否为2的n次方。实现代码如下:
算法性能分析:
这种方法的时间复杂度为O(1)。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。