在Python中检查给定数字是否为2的幂

Question

下面的代码不适用于某些输入。

a, i = set(), 1
while i <= 10000:
    a.add(i)
    i <<= 1

N = int(input())
if N in a:
    print("True")
else:
    print("False")

我的想法是，不是通过从1开始乘以2直到超过输入数字来检查每个输入是否为2的幂，而是在每一步进行比较，而是将所有2的幂存储在一组中以便检查O（1）中的给定输入。如何改善呢？

Answer 1

请参阅“如何检查数字是否为 2 的幂”的出色而详细的答案——对于 C#。同样使用“按位与”运算符&的等效 Python 实现是：

def is_power_of_two(n):
    return (n != 0) and (n & (n-1) == 0)

由于Python 具有任意精度整数，这适用于任何整数n，只要它适合内存。

简要总结上面引用的答案：第一项，在逻辑and运算符之前，简单地检查是否n不是 0——因此不是 2的幂。第二项通过确保后面的所有位来检查它是否是 2 的幂该按位&运算为 0。按位运算设计为仅True适用于 2 的幂——有一个例外：如果n（及其所有位）从 0 开始。

补充一点：作为对这两个术语的逻辑and“短路”的评估，如果在特定用例中，给定为 0 的可能性小于给定n为2的幂。

Answer 2

在二进制表示中，2 的幂是 1（一）后跟零。因此，如果数字的二进制表示形式只有一个 1，那么它就是 2 的幂。这里不需要检查num != 0：

print(1 == bin(num).count("1")) 

Answer 3

您是否故意避开图书馆？

如果没有，您可以使用math自己的力量（明白吗？力量……没关系）：

import math

math.log(n, 2).is_integer()

编辑1：或交替使用：

math.log2(n).is_integer()

值得一提的是，对于任何n <= 0人来说，都会抛出a，ValueError因为它在数学上是未定义的（因此不应出现逻辑问题）。

EDIT2：但是最好的方法是使用位操作：

(n & (n-1) == 0) and n != 0

说明：2的每个幂都将1位恰好设置为1（该数字的对数以2为底的索引-8的位为1000，因为2 ^ 3 = 8，所以将索引3中的位设置了）。因此，当从中减去1时，该位​​翻转为0，而所有在前位翻转为1。这使这2个数字彼此相反，因此对它们进行“与”运算时，结果将为0。因此，总而言之，每当我们从一个数字中减去一个，然后将其与结果相乘，然后变成0，则该数字就是2的幂。

EDIT1：计时

根据@FilipHaglund的评论，我回到了数学文档，尝试收集有关效率的信息。我发现log具有给定基数的方法实际上会计算出log(x)/log(base)明显较慢的方法。

比我看到的还有另一种方法-- log2仅需一个数字，显然可以计算其以2为底的对数，这听起来应该更快。

最后，我想看看它们与二进制方法的比较。因此结果是：

log带参数使用base=2：2.672359s

使用log2：2.114203s

使用二进制方法：1.352385s

下面是我用于这些措施的代码。我基本上要做的是检查1到1M之间的所有数字，每种方法是否都是2的幂，重复10次并求平均值。当然，这不是科学的，但可以提供一个想法...

EDIT2：还应注意，对于很大的数字（例如2**100），第一个log不准确，实际上给出了假负数。

math.log2(n).is_integer()

希望你发现我的一点研究有用:)

Answer 4

在 python 3.10 中，int.bit_count计算数字的设置位，因此我们可以使用：

n.bit_count() == 1