231-power-of-two.md

231. 2的幂:

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1
示例 2:

输入: 16
输出: true
解释: 24 = 16
示例 3:

输入: 218
输出: false

方法 1: 一次循环

思路

• 如果 n 为 2 的幂次方
  • 则 n 除以 2，应等于 // 整除，否则不是

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n < 0:
            return False
        if int(n) != n:
            return

        while n > 1:
            if n / 2 != n // 2:
                return False
            n //= 2

        return n == 1

复杂度分析

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

方法 2: 位运算

思路

• 可以先做个实验

for i in range(20):
    print(i, bin(i))

# 0 0b0
# 1 0b1   <==
# 2 0b10  <==
# 3 0b11
# 4 0b10  <==
# 5 0b101
# 6 0b110
# 7 0b111
# 8 0b1000  <==
# 9 0b1001
# 10 0b1010
# 11 0b1011
# 12 0b1100
# 13 0b1101
# 14 0b1110
# 15 0b1111
# 16 0b10000  <==
# 17 0b10001
# 18 0b10010
# 19 0b10011

• 不难看到 凡是 2 的幂次方，其二进制表示中， 有且只有 一个 1
  • 可根据这个特性来判断
• 就有以下两种思路
  • 1）根据 位 1 的个数，统计 1 的个数
  • 2）将二进制表示的最后一个 1 去除，如果剩下全部为 0，则为 2 的幂次方

# 1) 统计 1 的个数
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:

        # 2. 
        res = 0
        while n > 0:
            res += 1
            n &= (n - 1)
        return res == 1


# 2) 去除最后一个 1
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        return 0 == n & (n - 1)       

         
# 3) 对 2） 再优化一下
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and 0 == n & (n - 1)       

         

复杂度分析

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