原文链接: https://leetcode-cn.com/problems/power-of-two

英文原文

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

 

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

Example 4:

Input: n = 4
Output: true

Example 5:

Input: n = 5
Output: false

 

Constraints:

• -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

中文题目

给你一个整数 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

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

 

提示：

• -231 <= n <= 231 - 1

 

进阶：你能够不使用循环/递归解决此问题吗？

通过代码

高赞题解

解题思路：

• 若 $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

[]

class Solution {

    public boolean isPowerOfTwo(int n) {

        return n > 0 && (n & (n - 1)) == 0;

    }

}

统计信息

通过次数	提交次数	AC比率
182909	362411	50.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
位1的个数	简单
3的幂	简单
4的幂	简单