链接:https://leetcode-cn.com/problems/power-of-two/
标签:位运算、数学
题目
给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。
如果存在一个整数 x 使得 n == 2 ^ x ,则认为 n 是 2 的幂次方。
输入:n = 1 输出:true 解释:2^0 = 1 输入:n = 16 输出:true 解释:2^4 = 16 输入:n = 3 输出:false 输入:n = 4 输出:true 输入:n = 5 输出:false -231 <= n <= 231 - 1
分析
解法一:普通循环,超时。
解法二:列出2 ^ 0到2^30次方放到一个数组里,然后判断n是否在数组里。
解法三:2^x表示为二进制数,只有一位为1,其余位都为0,而n & (n - 1),则可以把n的最低位置0,所以利用这个特性,只需要将n和n - 1进行&运算然后判断结果是否为0即可。
编码
解法二:
class Solution { public boolean isPowerOfTwo(int n) { List<Double> list = Arrays.asList(Math.pow(2, 0), Math.pow(2, 1), Math.pow(2, 2), Math.pow(2, 3), Math.pow(2, 4), Math.pow(2, 5), Math.pow(2, 6), Math.pow(2, 7), Math.pow(2, 8), Math.pow(2, 9), Math.pow(2, 10), Math.pow(2, 11), Math.pow(2, 12), Math.pow(2, 13), Math.pow(2, 14), Math.pow(2, 15), Math.pow(2, 16), Math.pow(2, 17), Math.pow(2, 18), Math.pow(2, 19), Math.pow(2, 20), Math.pow(2, 21), Math.pow(2, 22), Math.pow(2, 23), Math.pow(2, 24), Math.pow(2, 25), Math.pow(2, 26), Math.pow(2, 27), Math.pow(2, 28), Math.pow(2, 29), Math.pow(2, 30)); return list.contains((double)n); } }
解法三:
class Solution { public boolean isPowerOfTwo(int n) { if (n <= 0) { return false; } return (n & (n - 1)) == 0; } }