如何检查给定的数字是否是 2 的幂? [英] How to check if a given number is a power of two?

问题描述

以下代码不适用于某些输入.

The code below isn't working right for some inputs.

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 直到超过输入数字，并在每一步进行比较.相反，我事先将 2 的所有幂存储在 set 中，以便检查 O(1) 中的给定输入.如何改进?

My initial idea was to check for each input if it's a power of 2 by starting from 1 and multiplying by 2 until exceeding the input number, comparing at each step. Instead, I store all the powers of 2 in a set beforehand, in order to check a given input in O(1). How can this be improved?

推荐答案

位操作

一种方法是使用位操作:

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

解释: 每个 2 的幂都恰好有 1 位设置为 1(该数字以 2 为底的对数索引中的位).所以当从它减去 1 时，该位翻转为 0，所有前面的位翻转为 1.这使得这两个数字互为倒数，因此当对它们进行 AND 运算时，我们将得到 0 作为结果.

Explanation: every power of 2 has exactly 1 bit set to 1 (the bit in that number's log base-2 index). So when subtracting 1 from it, that bit flips to 0 and all preceding bits flip to 1. That makes these 2 numbers the inverse of each other so when AND-ing them, we will get 0 as the result.

例如:

                    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

所以，总而言之，每当我们从一个数中减去 1，结果与该数本身相加，即变为 0 - 该数是 2 的幂！

So, in conclusion, whenever we subtract one from a number, AND the result with the number itself, and that becomes 0 - that number is a power of 2!

当然，任何与 0 的 AND 运算都会得到 0，所以我们添加了对 n != 0 的检查.

Of course, AND-ing anything with 0 will give 0, so we add the check for n != 0.

您总是可以使用一些数学函数，但请注意，如果不小心使用它们可能会导致不正确的结果:

You could always use some math functions, but notice that using them without care could cause incorrect results:

import math

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

或者:

math.log2(n).is_integer()

• 值得注意的是，对于任何 n <= 0，这两个函数都会抛出一个 ValueError，因为它在数学上是未定义的(因此不应该出现逻辑问题).
• Worth noting that for any n <= 0, both functions will throw a ValueError as it is mathematically undefined (and therefore shouldn't present a logical problem).

或者:

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(2**29, 2).is_integer() will give False
  • math.log2(2**49-1).is_integer() will give True
  • math.frexp(2**53+1)[0] == 0.5 will give True!!

  这是因为 math 函数使用浮点数，而那些具有 固有的准确性问题.

  This is because math functions use floats, and those have an inherent accuracy problem.

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

  According to the math docs, the log with a given base, actually calculates log(x)/log(base) which is obviously slow. log2 is said to be more accurate, and probably more efficient. Bit manipulations are simple operations, not calling any functions.

  所以结果是:

  log with base=2:0.67 秒

  log with base=2: 0.67 sec

  frexp:0.52 秒

  log2:0.37 秒

  位操作:0.2 秒

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

  The code I used for these measures can be recreated in this REPL.

  这篇关于如何检查给定的数字是否是 2 的幂?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！