一、题目
给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。
如果存在一个整数 x 使得 n == 2 ,则认为 n 是 2 的幂次方。
二、思路
1)位移判断
由于2的幂次方的数字,其二进制一定只有一位1,进行移位判断,当最低位为1且数字不等于1,则有其他位。不满足题意。
2)减一判断
根据上面的思路,由于num二进制只有一位1,那么(num-1)&num一定为零,不为零就不是2的幂次方。
三、代码
1)位移判断
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1 && n != 1) {
return false;
}
n = n >> 1;
}
return true;
}
}
2)减一判断
class Solution {
public boolean isPowerOfTwo(int n) {
return ((n > 0) && (((n-1)&n) == 0));
}
}
时间复杂度为O(1),空间复杂度为O(1)。