题目描述:
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 20 = 1
思路:注意2的幂次方数有一个特点,就是化位二进制后,它只有最高位一个1。所以,可以借用之前“1的个数”的想法,把它的1的个数数出来。代码如下:
bool isPowerOfTwo(int n) {
//不可能是2的幂次方的情况先排除
//因为n是要-1的,负数可能引发奇怪的结果。
if(n<=0) return false;
int count=0;
while(n)
{
count++;
n&=n-1;
}
return count==1;
}
这个应该算是O(n)的时间复杂度,测试运行时间 4ms。但其实没有必要把它所有的1都数出来。我们只需要知道,它是不是只含有一个1就行了!也就是,去掉一个1之后,它还有1吗?有的话就是false。代码如下:
bool isPowerOfTwo(int n) {
if(n<=0) return false;
//去掉1个1
return n&(n-1)? false: true;
}
O(1)的时间复杂度,应该是最简洁的办法了。不过测试运行时间还是 4ms。
;