LeetCode 算法 每日一题 231.2的幂

231.2的幂

题目描述

给你一个整数n，请你判断该整数是否是 2 的幂次方。如果是，返回true；否则，返回false。
如果存在一个整数x使得n == 2^x，则认为 n 是 2 的幂次方。

示例1

输入：n = 1
输出：true
解释：2⁰ = 1

示例2

输入：n = 16
输出：true
解释：2⁴ = 16

示例3

输入：n = 3
输出：false

示例4

输入：n = 4
输出：true

示例5

输入：n = 5
输出：false

提示

• -2³¹ <= n <= 2³⁰ - 1
• 你能够不使用循环/递归解决此问题吗？

十进制	二进制	十进制	二进制	十进制	二进制(计算机负数:补码形式)
20	0000 0001	20 - 1	0000 0000	-20	1111 1111
21	0000 0010	21 - 1	0000 0001	-21	1111 1110
22	0000 0100	22 - 1	0000 0011	-22	1111 1100
23	0000 1000	23 - 1	0000 0111	-23	1111 1000
24	0001 0000	24 - 1	0000 1111	-24	1111 0000

2的n次幂在二进制中就是其中的1左移n位，题目最大范围为2³⁰，可以得出

• 2ⁿ & （2ⁿ - 1） == 0
• 2ⁿ & （-2ⁿ） == 2ⁿ
• 2³⁰ % 2ⁿ == 0

代码演示
Java 位运算

public class OneQuestionPerDay231 {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isPowerOfTwo(1));
        System.out.println(s.isPowerOfTwo(16));
        System.out.println(s.isPowerOfTwo(3));
        System.out.println(s.isPowerOfTwo(4));
        System.out.println(s.isPowerOfTwo(5));
    }
}

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

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

class Solution_3 {
    static final int MAX = 1 << 30;
    public boolean isPowerOfTwo(int n) {
        return n > 0 && MAX % n == 0;
    }
}

Java 2ⁿ&(2ⁿ-1)=0 提交结果
执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35.6 MB, 在所有 Java 提交中击败了36.01% 的用户
Java 2ⁿ&(-2ⁿ)=2ⁿ 提交结果
执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35.2 MB, 在所有 Java 提交中击败了92.65% 的用户
Java 2³⁰%2ⁿ=0 提交结果
执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35.4 MB, 在所有 Java 提交中击败了71.11% 的用户

这时候更能明白计算机补码存在的道理了