6.2  如何判断一个数是否为2的n次方

6.2 如何判断一个数是否为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次方

算法性能分析：

上述算法的时间复杂度为O（（log2ⁿ）。

方法二：与操作法

那么是否存在效率更高的算法呢？通过对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）。