【LeetCode】2的幂
原题信息如下所示:
给你一个整数
n
,请你判断该整数是否是 2 的幂次方。如果是,返回true
;否则,返回false
。如果存在一个整数
x
使得n == 2x
,则认为n
是 2 的幂次方。
n的取值范围:
-2^31 <= n <= 2^31-1
输入:n = 1 输出:true 解释:20 = 1 输入:n = 16 输出:true 解释:24 = 16 输入:n = 3 输出:false
看到这个题的第一想法是什么呢?
1、判断是不是2
的幂,那不就是判断这个数能不能被2
整除嘛
2、使用循环做除以2
的操作,终止条件:商为0
,
3、除法期间,判断余数是不是1
,如果出现1
,那么这个数就不能被2
整除了
4、没有出现1
,那么就是2
的幂
代码:
public boolean isPowerOfTwo(int n) { if (n<=0) return false; if (n==1) return true; while (n > 1) { if ((n % 2) == 1) return false; n = n >> 1; } return true; }
- 时间复杂度为
O(logn)
- 空间复杂度为
O(1)
这样也不是不能解决问题,那么我们能不能不用循环呢?
在leetcode官解中看到一个取巧的方法,从 n 的取值,可以看出最大值为 2^31-1
,那么2的幂最大值则为 2^30
,也就表示用 2^30
去除以 n
,余数为0
,这个数就是2
的幂
代码:
static final int BIG = 1 << 30; public boolean isPowerOfTwo(int n) { return n > 0 && BIG % n == 0; }
- 时间复杂度:
O(1)
。 - 空间复杂度:
O(1)
。
那么是不是还有更更更加优雅的解法呢?
这还真的有!
可以使用二进制,一个数是2
的幂,那么这个数转化成二进制以后,这里面一定只有一个1
,其余位数全是0。
我们可以利用一下这个特点,假如我们把这个1
去掉,然后判断其他位是不是0
就可以了
我们可以使用位运算,使用 & 按位运算:n & (n-1)
4 转化成二进制是 0100,当4做减一操作以后,二进制数变成了0011
,这时候进行 & 操作,最后的结果一定是 0 。
如果一个数不是2
的幂,那么转化成二进制以后,里面最少有 2
个1
的存在,例如 5 转化成二进制位 0101
,当 5 做减一操作以后,二进制数变成了0100
,这个数跟原数进行按位与操作,因为最高位上的1
没有改变,所以结果不是0
代码
public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
- 时间复杂度:
O(1)
。 - 空间复杂度:
O(1)
。
负数的补码在计算机中是按照补码的方式存储的,然后你想想这个是不是也可以优雅的操作一波呢?
另外在leetcode评论区看到一个更有趣的解法,你来品一品~
END
这个题不难,官方给出的是简单类型,暴力解法也不会超时,但是却有更加优雅的方式。
第一次看到这个题目的时候,想到了转化二进制,却没有想到二进制的运算,对计算机中的二进制的知识还有欠缺,对原码、反码、补码了解不多,看来做算法题还需要加强这方面的训练。