题目描述
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
样例
输入: 1
输出: true
解释: 20 = 1
输入: 16
输出: true
解释: 24 = 16
输入: 218
输出: false
算法1
模拟
- 每次若该数整除
2
,则对该数进行整除,最后判断该数最后是否是1
时间复杂度 $O(logn)$
Java 代码
class Solution {
public boolean isPowerOfTwo(int n) {
while(n > 0 && n % 2 == 0)
{
n /= 2;
}
return n == 1;
}
}
算法2
位运算
- 1、返回
n
的最后一位1
:lowbit(n) = n & -n
- 2、若
n
的最后一位1
对应的二进制恰好是n
,则说明n
是2
的幂
时间复杂度 $O(1)$
Java 代码
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
}