给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。
如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。
示例 1:
输入:n = 1
输出:true
解释:20 = 1
示例 2:
输入:n = 16
输出:true
解释:24 = 16
示例 3:
输入:n = 3
输出:false
示例 4:
输入:n = 4
输出:true
方法一
bitCount(int i) 函数,实现统计一个数的二进制位有多少个 1 。如 5 的二进制为 101,返回 2。
class Solution { public boolean isPowerOfTwo(int n) { return n<0? false:Integer.bitCount(n) == 1; } }
方法二
如果 n 是 4 的幂,那么它可以表示成 4x的形式,我们可以发现它除以 3的余数一定为 1,即:
如果 n 是 2 的幂却不是 4 的幂,那么它可以表示成 4x×2 的形式,此时它除以 3 的余数一定为 2。
因此我们可以通过 n 除以 3 的余数是否为 1 来判断 n 是否是 4 的幂。
class Solution { public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; } }
方法三 递归
如果num是4的幂,我们让他不停的除以4,最终结果一定是1,如果计算的过程中,不是1也不能被4整除,直接返回false,代码如下
public boolean isPowerOfFour(int num) { //负数不可能是4的幂 if (num <= 0) return false; //1也是4的幂 if (num == 1) return true; //如果不能够被4整除,肯定不是4的幂 if (num % 4 != 0) return false; //如果能被4整除,除以4然后递归调用 return isPowerOfFour(num / 4); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)