2 的幂

LeetCode原题链接

题目

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。
要求不用循环/递归方式求解。

示例1

输入：n = 1
输出：true
解释：2^0 = 1

示例2

输入：n = 16
输出：true
解释：2^4 = 16

解法

如果用循环来做，那就很简单，不断除2去判断即可。
在不能用循环解题时，需要从数字规律角度去看待，一般比较容易想到转为2进制去想。一个数如果是2的整数幂，那其2进制表示时，一定有且仅有一个1。比如 (2)₁₀ = (10)₂ , (16)₁₀ = (10000)₂ 。那问题就可以转化为如何判断一个2进制数中1的个数。
这个判断可以通过一个位运算公式来实现：n&(n-1)。这个公式能够把n的2进制表示法里面的最末尾的1去掉，如果这个运算完，n等于0，那就可以说明n原先只有1一个1，那就符合2的幂，反之不行。

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

（另外，其实查表法也是可以的。。直接先构建一个map，直接查，毕竟n不大的情况下，2的幂也没几个数。）