星星之火-判断一个数是否是2的幂

本文最后更新于：January 27, 2022 pm

积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

目录

题目

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

思路

1.自己思路

将二进制位一位一位的移动进行比较。

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n<0) return false;
        for(int i=0;i<34;++i){
            if((1<<i)==n) return true;
        }
        return false;
    }
}

效率：

1
2
3
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.3 MB, 在所有 Java 提交中击败了79.26%的用户
通过测试用例：1108 / 1108

2.二进制表示

一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1。使用位运算，将 n 的二进制表示中最低位的那个 1 提取出来，再判断剩余的数值是否为 0 即可。简单说就是，一个数的二进制位中只有一个1，其余都是0。这样的数就是符合的。

两种常见的与「二进制表示中最低位」相关的位运算技巧。

  1. 第一种
1
2
n & (n - 1)
如果 n 是正整数并且 n & (n - 1) = 0，那么 n 就是 2 的幂。

解释：

1
2
3
    A:0001000   //8
B=A-1:0000111   //7
  A&B:0000000

效率：

1
2
3
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.2 MB, 在所有 Java 提交中击败了95.52%的用户
通过测试用例：1108 / 1108
  1. 第二种
1
2
n & (-n)
其中 −n 是 n 的相反数，是一个负数。该位运算技巧可以直接获取 n 二进制表示的最低位的 1。

解释：
由于负数是按照补码规则在计算机中存储的，−n 的二进制表示为 n 的二进制表示的每一位取反再加上 1，如果 n 是正整数并且 n & (-n) = n，那么 n 就是 2 的幂。如：

1
2
3
4
5
6
7
8
9
10
     A:0001000
A的补码:1110111 + 1
       1111000 //这样我们就获取了 n 二进制表示的最低位的 1。
A&(-A):0001000 //是等于A的


     B:0001100
B的补码:1110011 + 1
       1110100
B&(-B):1110000 //是不等于B的

效率：

1
2
3
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.2 MB, 在所有 Java 提交中击败了91.12%的用户
通过测试用例：1108 / 1108

时间复杂度：O(1)。
空间复杂度：O(1)。

3.判断是否为最大 2 的幂的约数

在题目给定的 32 位有符号整数的范围内，最大的 2 的幂为 230 = 10737418242 。我们只需要判断 n 是否是 230的约数即可。

1
2
3
4
5
6
class Solution {
    static final int BIG = 1 << 30;
    public boolean isPowerOfTwo(int n) {
        return n > 0 && BIG % n == 0;
    }
}

效率：

1
2
3
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.3 MB, 在所有 Java 提交中击败了82.10%的用户
通过测试用例：1108 / 1108

时间复杂度：O(1)。
空间复杂度：O(1)。