LeetCode

Appearance

[231] 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

 

Constraints:

  • -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?
Related Topics
  • 位运算
  • 递归
  • 数学

  • 👍 749
  • 👎 0

    • 思路 ​

    使用位运算，理解2的幂一定是最左边数字为1，剩下位数为 0 例如 4的二进制为 100，而 3 的二进制是 011, 4 & 3 = 0

    text
    011
111
---
000

    011

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n  > 0 and n&(n-1) == 0
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度O(1)
    • 空间复杂度O(1)