题目

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1 输出：true 解释：20 = 1

示例 2：

输入：n = 16 输出：true 解释：24 = 16

示例 3：

输入：n = 3 输出：false

提示：

• -2^31 <= n <= 2^31 - 1

解题思路

题意分析

首先，我们要明确“2的幂次方”的特点：

1. 必须是正数：2^x 永远大于 0，所以如果 n <= 0，可以直接返回 false。
2. 二进制特征：观察一下2的幂次方的二进制表示：
   • 1 (2^0) -> 00000001
   • 2 (2^1) -> 00000010
   • 4 (2^2) -> 00000100
   • 8 (2^3) -> 00001000
   • 16 (2^4) -> 00010000

你会发现一个非常关键的规律：一个数如果是2的幂次方，那么它的二进制表示中，有且仅有一位是 1，其余所有位都是 0。

解题方法

如果一个数 n 是2的幂次方，它的二进制只有一个 1。

• n = 8 (二进制 1000)
• n - 1 = 7 (二进制 0111)

将 n 和 n - 1 进行按位与（AND）运算 (&)：

  1000  (n)
& 0111  (n - 1)
------
  0000  (结果为 0)

n & (n - 1) 的结果是 0。这个规律适用于所有2的幂次方。

如果一个数不是2的幂次方（即二进制中有多个1），例如 n = 12 (二进制 1100)：

• n - 1 = 11 (二进制 1011)
• n & (n - 1):

  1100  (n)
& 1011  (n - 1)
------
  1000  (结果为 8，不为 0)

结果不为0。

具体代码

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