231. Power of Two

Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

Input: 16
Output: true
Explanation: 24 = 16

Example 3:

Input: 218 Output: false

---

判断一个数是否是2的幂次方。 递归或迭代等常规方法就不说了，可以参考LeetCode Power of Three。网上看到两个比较有意思的解法，和位运算有关。下面列出了2的幂次方以及对应的二进制表示，先找找规律。

• 1:1
• 2:10
• 4:100
• 8:1000
• 16:10000

发现所有2的幂的二进制中都只有1位是1，所有可以统计二进制中1出现的次数，等于1表示是2的幂。完整代码如下：

class Solution {
public:
    bool isPowerOfTwo(int n)
    {
        int cnt = 0;
        while (n > 0) {
            cnt += (n & 1);
            n >>= 1;
        }
        return cnt == 1;
    }
};

本代码提交AC，用时3MS。
另外，不考虑前导零（leading zero），这些2的幂只有最高位是1，如果把这个数减1，那么最高位变为0了，后面的位全变为1。把前后的两个二进制相与，正好等于0，比如$4_2=100$，$4-1=3_2=011$，$4\&3=100\&011=000$。这个思路的完整代码只需一行，如下：

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

本代码提交AC，用时6MS，按理应该要比上一种解法快，不知为何。

二刷。解法太多了，直接1移位判断相等即可：

class Solution {
public:
    bool isPowerOfTwo(int n) {
        int one=1;
        for(int i=0;i<31;++i){
            int cur = one << i;
            if(cur==n)return true;
        }
        return false;
    }
};

本代码提交AC，用时0MS。