题目描述

思路介绍

个人思路：
判断一个整数是否是2的n次方，可以通过位运算的方法，2ⁿ可以表现为1左移n位（如0x1=2⁰=1<<0，0x2=2¹=1<<1，0x8=2³=1<<3，…），所以，只要一个整数对应的二进制形式中1的个数为1，则这个数为2的n次方。（虽然负数的二进制形式中最高位为1，但2ⁿ一定比0大，所以不用考虑负整数的情况）

我的第一次正确提交

bool isPowerOfTwo(int n)
{
    int cnt = 0;
    if(n < 0)
        return false;
    while(n)
    {
        if((n & 0x1) == 1)
            cnt++;
        n >>= 1;
    }
    if(cnt == 1)
        return  true;
    return false;
}

在这里插入图片描述

官方版本

方法一：二进制表示

一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1。
因此我们可以考虑使用位运算，将 n 的二进制表示中最低位的那个 1 提取出来，再判断剩余的数值是否为 0 即可。下面介绍两种常见的与「二进制表示中最低位」相关的位运算技巧。
第一个技巧是 n & (n - 1)【其中& 表示按位与运算。该位运算技巧可以直接将 n 二进制表示的最低位 1 移除】
如果 n 是正整数并且 n & (n - 1) = 0，那么 n 就是 2 的幂，原理见官方题解（链接见后文）
第二个技巧是第二个技巧是n & (-n) 【其中 ?n 是 n 的相反数，是一个负数。该位运算技巧可以直接获取 n 二进制表示的最低位的 1】
如果 n 是正整数并且 n & (-n) = n，那么 n 就是 2 的幂，原理见官方题解（链接见后文）
——作者：LeetCode-Solution——链接——来源：力扣（LeetCode）

技巧一对应代码

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

技巧二对应代码

bool isPowerOfTwo(int n) {
    return n > 0 && (n & -n) == n;
}

复杂度分析
时间复杂度：O(1)。
空间复杂度：O(1)。

方法二：判断是否为最大 2 的幂的约数

除了使用二进制表示判断之外，还有一种较为取巧的做法。
在题目给定的 32 位有符号整数的范围内，最大的 2 的幂为 2³⁰ = 10737418242 。我们只需要判断 n 是否是 2³⁰ 的约数即可。
——作者：LeetCode-Solution——链接——来源：力扣（LeetCode）

const int BIG = 1 << 30;

bool isPowerOfTwo(int n) {
    return n > 0 && BIG % n == 0;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/power-of-two/solution/2de-mi-by-leetcode-solution-rny3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(1)。
空间复杂度：O(1)。

下面是我的一个失败的提交记录
由于我的循环结束条件是n为0，但负数最高位为1，所以循环不会停止，当循环到32次后，出现了越界报错。

bool isPowerOfTwo(int n)
{
    int cnt = 0;
    while(n)
    {
        if((n & 0x1) == 1)
            cnt++;
        n >>= 1;
    }
    if(cnt == 1)
        return  true;
    return false;
}