我正在尝试使用递归查找数字是否为 2 的幂。但是，我似乎无法找出正确的解决方案。到目前为止，这是我尝试过的:
def is_power(n):
n = n/2
if n == 2:
return True
elif n > 2:
is_power(n)
else:
return False
if is_power(32):
print 'yes'
else:
print 'no'
因为“32”是 2 的幂，我希望我的代码返回"is"作为输出。但是，代码会输出“no”。我的代码似乎有什么问题？
请您参考如下方法:
因为我在这里已经有了一个可接受的答案，所以我将用这个来解释一下为什么你的方法不好:
它在 python 中使用递归。Python 需要为每次调用打开一个堆栈框架，因此对于非常大的数字，这将不是解决此问题的好方法。对于非常大的整数，它甚至会失败。
我什至不认为像 python 这样的非纯函数式语言中的递归是在这里做的直观的事情。有一百万种更简单的方法可以做到这一点；例如，while 循环:
n = int(n)
while n>1:
if n/2 != n/2.0: #compare integer division to float division
return False
n = n/2
return True
检查 2 的幂 可以通过了解计算机上整数的存储结构是什么来以巧妙的方式完成:它是二进制的。因此，您可以只计算 int 二进制表示中的二进制 1:
return bin(n).count('1') == 1
也可以。当然，这意味着 python 在内部将整数转换为字符串，这会浪费大量内存。所以你不妨
power_of_2 = 1
while power_of_2 <= n:
if power_of_2 == n:
return True
power_of_2 *= 2
return False
只是将您的数字与所有小于或等于 2 的幂进行比较。 (这当然可能需要更长的时间并使用更多的内存，因为你的 python 解释器将不得不解释 python 而不是仅仅将你的整数转换为 C 中的字符串，但这是关于算法原理，对吧？)这样，你不不需要保留内存来计算二进制表示中 1 的出现次数。
当然，有一种方法可以解决您的问题，我从 things I've learned 中获取它用 C/C++ 编写:
bool(n and not (n&(n-1)))
为了解释 n 而不是 (n&(n-1)):n 为真当且仅当 n != 0，这就是否则错误地符合 2 的幂。
对于 not (n&(n-1)):n&(n-1) 检查是否不是 2 的幂，所以我们必须反转它。 & 是按位“与”运算符。要理解 n & (n-1)，假设 n 是 2 的幂，比方说 8。所以 n-1 == 7，因此
8|0b1000
7|0b0111
--------
&|0b0000
如您所见，对于 2 的所有幂，n&(n-1) 是 0，计算结果为 False。对于 2 的所有非幂，减去 1 时不会反转所有位，因此 n&(n-1) != 0，计算结果为正确。
