题目
难度：★☆☆☆☆
类型：数学
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例
示例 1:
输入: 1
输出: true
解释: 2^0 = 1
示例 2:
输入: 16
输出: true
解释: 2^4 = 16
示例 3:
输入: 218
输出: false
解答
这是一道很简答的数学题，输入数字n如果是2的幂，则满足条件：把n除以2得到的余数一定为零，除数一定是2的幂，我们这里分别使用迭代法和递归法进行判断。
方案1：迭代
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
while n and n != 1: # 当n大于零且n不为1时
r, n = n % 2, n // 2 # n除以2获得余数和除数
if r != 0: # 只要余数不为零
return False # 一定不是2的幂
return n == 1 # 如果是2的幂，跳出循环时应该返回1
方案2：递归
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
if n < 2: # 递归跳出条件
return n > 0 # 如果n为零或负数，返回False，n为1，返回True
# 要求余数为零，除数也是2的幂，输入数字才能是2的幂
return n % 2 == 0 and self.isPowerOfTwo(n // 2)
看样子递归比迭代简洁一点。
方案3：二进制计算
我们将输入数字转为二进制，如果输入数字n是2的幂，那么n的二进制形态上只有最高位是“1”，其他位均为“0”，而n-1的二次幂最高位变成了“0”：，而其他位均为“1”，因此我们把n的二进制与n-1的二进制按位相与得到的结果一定是零。根据这个原理，我们可以判断输入数字是否是2的幂。这里需要注意的是，0不是2的幂，因此我们要加一个输入非零的限制。
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
return n and n & (n-1) == 0
如有疑问或建议，欢迎评论区留言~
