每日算法一题之判断一个数是否是2的n次方

题目：如何判断一个数是否是2的n次方，要求时间复杂度为O(1).

常规数学解法：

function isPowerOfTwo(n){
    if(n > 0){
      while(n > 1){
       if(n%2 == 0){
        n = n / 2;
       }else{
        return false;
       }
    }
    return true;
    }else{
    return false;
    }
}

如果面试官看见你写出这样的代码，可能印象就会大打折扣，因为时间复杂度不是O(1),虽然解法没问题，那么我们要往编程方面换个思路。

思路：考察的是位运算，尤其是对二进制的理解；当一个数为2的n 次方时，整个二进制数，只有他本位是1 其他位为0，如果我们给这个数减一，那么本位变为0 其他位全部变成1；我们可以通过&运算，如果为0即为2的n次方; 本题暂不讨论n为分数（既浮点数）的情况。

例子：我们通过8来进行举例他是2的3次方。

0 0 0 0 1 0 0 0 //数字8
0 0 0 0 0 1 1 1 //数字7
0 0 0 0 0 0 0 0 //&运算的结果

代码实现：

public static  boolean isPowerOfTwo(int n){

   return n > 0 && (n & n - 1) == 0;
}

参考资料：