231. 2的幂

方法一、对于循环除以2，直到结果为奇数，判断结果是否为1

时间O(logn)，(这里题目已经给出了n得范围必然是int，那么logn其实必然小于31)

1 class Solution {
2     public boolean isPowerOfTwo(int n) {
3         if(n==0) return false;
4         while(n%2==0){
5             n/=2;
6         }
7         return n==1;
8     }
9 }

变形,上面我们从n递推至1，下面得变形我们从1通过位运算递推至2^31判断

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

方法二、利用一次位运算

之前我们做过 191. 位1的个数这道题，当时得出结果，n&(n-1)，

可以将n最右侧得1置为0，如此循环我们就可以计算出n中有多少个1，

这里需要判断n是否为2得幂，基于其特性n必然只存在1位为1，

那么必然有n&(n-1)=0，于是有

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

231. 2的幂

相关推荐