231-2的幂

2的幂

一、题目描述

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

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

二、示例

1、示例一

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

2. 示例二

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

3. 示例三

$$输入：n = 3\\ 输出：false$$

4.示例四

$$输入：n = 4\\ 输出：true$$

三、解题思路

• 若$n = 2 ^ x$且x为自然数（即 n 为2的幂），则一定满足以下条件：
  1. 恒有n & (n - 1) == 0, 这是因为：
     • n二进制最高位为1, 其余所有位为0。
     • n - 1二进制最高位为0，其余所有位为1。
  2. 一定满足n > 0。
• 因此，通过n > 0且n & (n - 1) == 0 即可判定是否满足$n == 2^x$。

$2^x$	n	n - 1	n & (n - 1)
$2^0$	0001	0000	(0001) & (0000) = 0
$2^1$	0010	0001	(0010) & (0001) == 0
$2^2$	0100	0011	(0100) & (0011) == 0
$2^3$	1000	0111	(1000) & (0111) == 0
…	…	…	…

四、代码

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (n - 1) == 0