如何检查给定数字是否为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")

我最初的想法是检查每个输入是否为2的幂，方法是从1开始乘以2直到超过输入数量，然后在每个步骤进行比较。相反，我set预先存储了2的所有幂，以便检查中的给定输入O(1)。如何改善呢？

Answer 1

将 _ 最好的，最准确_ 的方法是使用位操作：

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

说明：
2的每个幂将1位恰好设置为1（该数的对数以2为底的索引中的位）。因此，当从中减去1时，该位​​翻转为0，而所有在前位翻转为1。这使这2个数字互为逆，因此对它们进行“与”运算时，结果将为0。

例如：

                    n = 8

decimal |   8 = 2**3   |  8 - 1 = 7   |   8 & 7 = 0
        |          ^   |              |
binary  |   1 0 0 0    |   0 1 1 1    |    1 0 0 0
        |   ^          |              |  & 0 1 1 1
index   |   3 2 1 0    |              |    -------
                                           0 0 0 0
-----------------------------------------------------
                    n = 5

decimal | 5 = 2**2 + 1 |  5 - 1 = 4   |   5 & 4 = 4
        |              |              |
binary  |    1 0 1     |    1 0 0     |    1 0 1
        |              |              |  & 1 0 0
index   |    2 1 0     |              |    ------
                                           1 0 0

因此，总而言之，每当我们从一个数字中减去一个，然后将结果与数字本身相减，即为0-该数字就是2的幂！

当然，0将任何与进行AND运算都会得到0，因此我们添加的校验n != 0。

您总是可以使用一些math函数，但是这些函数的准确性较差：

import math

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

要么：

math.log2(n).is_integer()

• 值得注意的是，对于任何n <= 0函数，两个函数都将抛出a，ValueError因为它在数学上是未定义的（因此不应出现逻辑问题）。

要么：

abs(math.frexp(n)[0]) == 0.5

• 还应该指出的是，对于某些数字，这些功能不准确，实际上给出了 假结果 ：

  • math.log(2**29, 2).is_integer() 会给 False
  • math.log2(2**49-1).is_integer() 会给 True
  • math.frexp(2**53+1)[0] == 0.5会给True！

这是因为math函数使用浮点数，而这些浮点数具有固有的精度问题。

根据数学文档，log具有给定基数的，实际上会计算出log(x)/log(base)这显然很慢。log2据说更准确，甚至可能更有效。位操作是简单的操作，不调用任何函数。

结果是：

log与base=2：0.67秒

frexp：0.52秒

log2：0.37秒

位操作：0.2秒

我用于这些措施的代码可以在此REPL中重新创建。