06
07/2015
[LeetCode] Power of Two
Power of Two
Given an integer, write a function to determine if it is a power of two.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
解题思路：
这道题的题意是判断一个数是不是2的幂。有几个问题需要确定一下：
1、1也是2的幂，是0次幂
2、将一个整数向左移一位，相当于这个整数乘以2，向右移一位，相当于该整数除以2
3、注意大整数的溢出情况。
下面是代码：
class Solution {
public:
bool isPowerOfTwo(int n) {
long long num = 1;
while(num <= n){
if(num==n){ //先判断，考虑到1的情况
return true;
}
num = num << 1;
}
return false;
}
};update in 2015-07-08
感谢网友的提出新的方法。上述方法的时间复杂度为：O(logn)。有没有更快的方法？注意到2的幂的倍数的二进制有一个特点，最高位为1，其余位为零。于是可以判断某个数的二进制表示是否只有一个1，若只有一个1，则为2的幂，否则不是。对于正整数，n&(n-1)表示去除n的二进制表示的最后一个1，若n&(n-1)==0，则n为2的幂。
注意对于0和负数，都不是2的幂。此方法的时间复杂度为O(1)。
class Solution {
public:
bool isPowerOfTwo(int n) {
if(n<=0){
return false;
}
return (n&(n-1))==0;
}
};转载请注明：康瑞部落 » [LeetCode] Power of Two
0 条评论