Fork me on GitHub

leetcode之231. 2的幂

发表于 | 分类于
字数统计 209 字 | 阅读时长 1 分钟

题目描述：

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

1
2
3
4
> 输入: 1
> 输出: true
> 解释: 20 = 1
>

示例 2:

1
2
3
4
> 输入: 16
> 输出: true
> 解释: 24 = 16
>

示例 3:

1
2
3
> 输入: 218
> 输出: false
>

解题思路一：

与运算

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0)  return false;
        
        return (n & (n - 1)) == 0? true:false;
        
    }
};

解题思路二：

运用数学计算
loga b = log10 b / log10 a 就可以运用这个计算，如果是2的幂， 就是log2 n为整数

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	bool isPowerOfTwo(int n) 
	{
		if (n <= 0)
			return false;
		double tmp = log10(n) / log10(2);
		if (tmp - int(tmp) == 0)
			return true;
		return false;
	}
};