231. Power of Two

题目描述和难度

  • 题目描述：

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

示例 1:

输入: 1
输出: true

示例 2:

输入: 16
输出: true

示例 3:

输入: 218
输出: false

思路分析

求解关键：方法很多，给出几个比较好理解的。我个人觉得主要的考点还是在位运算的一些性质上。

参考解答

参考解答1：可能是最简单的一个版本吧，n & (n - 1) 运算，能把一个二进制数最右边的 1 变成 0，这一点应该作为一条基本性质记住。

public class Solution {

    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

参考解答2：该方法可以用于整除判断。

public class Solution2 {

    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 2 == 0) {
            n /= 2;
        }
        return n == 1;
    }
}

参考解答3：用到了 Java 库函数，并且还可以根据此法判定一个数是否是 3 的方幂、4 的方幂等等。

public class Solution3 {

    public boolean isPowerOfTwo(int n) {
        return n > 0 && Integer.toString(n, 2).matches("^10*$");
    }
}

参考解答4：打表法，把所有可能的结果都例举出来。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Solution4 {

    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        // 比 Integer.MAX_VALUE 小的所有的整数中 2 的方幂的所有的数
        int[] nums = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        return set.contains(n);
    }

    // 该 main 方法可以得到整型范围内所有的 2 的方幂
    public static void main(String[] args) {
        int i = 1;
        List<Integer> list = new ArrayList<>();
        while (i > 0 && i < Integer.MAX_VALUE) {
            list.add(i);
            i *= 2;
        }
        System.out.println(list);
    }
}

参考解答5：该方法对于判定质数的方幂同样有效，例如判定一个数是否是 3 的方幂，不过得事先计算出在允许的范围内 3 的方幂的最大者。

public class Solution5 {

    public boolean isPowerOfTwo(int n) {
        // 1073741824 是小于 Integer.MAX_VALUE 中 2 的方幂的最大者
        return n > 0 && 1073741824 % n == 0;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0231-power-of-two ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。