栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

如何检查给定数字是否为2的幂?

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

如何检查给定数字是否为2的幂?

将 _ 最好的,最准确_ 的方法是使用位操作:

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

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

例如:

         n = 8decimal |   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 1index   |   3 2 1 0    |   |    -------          0 0 0 0-----------------------------------------------------         n = 5decimal | 5 = 2**2 + 1 |  5 - 1 = 4   |   5 & 4 = 4        |   |   |binary  |    1 0 1     |    1 0 0     |    1 0 1        |   |   |  & 1 0 0index   |    2 1 0     |   |    ------          1 0 0

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

当然,

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


您总是可以使用一些

math
函数,但是这些函数的准确性较差:

import mathmath.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中重新创建。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/641052.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号