添加链接 注册    登录
link之家
链接快照平台
  • 输入网页链接，自动生成快照
  • 标签化管理网页链接
相关文章推荐
迷茫的火龙果  ·  boost::any浅析 - 明明1109 ...·  3 月前    · 
有情有义的馒头  ·  Matplotlib绘图双纵坐标轴设置及控制 ...·  1 年前    · 
苦恼的跑步机  ·  连接到 SAP - Azure Logic ...·  1 年前    · 
英姿勃勃的松鼠  ·  HTML ...·  1 年前    · 
善良的牙膏  ·  测试开发之网络篇-常用命令_ITPUB博客·  1 年前    · 
link之家  ›  使用递归查找一个数字是否是2的幂
python python for循环 递归算法 递归函数
https://www.qiniu.com/qfans/qnso-29480680
另类的牛肉面
11 月前
七牛云社区 牛问答 使用递归查找一个数字是否是2的幂

使用递归查找一个数字是否是2的幂

5 人关注

我试图用递归的方法找出一个数字是否是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的幂，我预计我的代码会返回'是'作为输出。然而，代码的输出是'no'。我的代码似乎出了什么问题？
2 个评论
chepner ：
提示：你已经实现了（或多或少） is_even ，而不是 is_power （至少，在 Python 3 中）。
will ：
1对你来说不算是一个答案吗（即 2**0 ）？
python
python-2.7
recursion
Manas Chaturvedi
Manas Chaturvedi
发布于 2015-04-07
9 个回答
Marcus Müller
Marcus Müller
发布于 2020-07-30
已采纳
0 人赞同

既然我这里已经有了一个公认的答案，我就用这个答案来解释一下为什么你的方法不好。

It uses recursion in python. Python需要为每个调用打开一个堆栈帧，所以对于非常大的数字，这将是一个糟糕的解决方法。对于非常大的整数，它甚至会失败。

I don't even think 非纯功能语言中的递归 在这里，像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

对照二的幂的检查通过认识到计算机上整数的存储结构是什么，可以用巧妙的方式来完成：它是二进制的。所以你可以在你的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的出现次数了。


当然，有一个单行本可以解决你的问题，我把它从我学到的东西 writing in C/C++:


bool(n and not (n&(n-1)))

为了解释n and not (n&(n-1))。如果n是真的，那么n != 0就是真的，否则它就会被错误地定性为2的幂。


For not (n&(n-1)): n&(n-1) checks whether something is not是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，其值为True。
mrgloom ：
这个 if n/2 != n/2.0: 在python 3中会失效，可以修改为 if n // 2 != n / 2 。
Marcus Müller
Marcus Müller
发布于 2020-07-30
0 人赞同 
elif n > 2:
    is_power(n)

is missing the return:


def is_power(n):
    n = n/2
    if n == 2:
        return True
    elif n > 2:
        return is_power(n)
    else:
        return False

因此，is_power的 "第一层 "没有返回任何东西（或None，取决于你如何检查），这导致了no的输出。


@kaveman正确地指出了is_power(2)产生的错误结果。
你可以通过在elif子句中把2减半来解决这个问题。


def is_power(n):
    if not n == int(n):
        return False
    n = int(n)
    if n == 1:
        return True
    elif n > 2:
        return is_power(n/2.0)
    else:
        return False

EDIT:@will指出，我把Python2和Python3的划分混为一谈。使用/2.0可以解决这个问题。另外，在对问题的评论中，他指出1是2的幂，用==1而不是==2进行检查解决了这个问题。另外，我还添加了一个int，这对于2的幂的检查是没有必要的（因为IEEE754浮点数毕竟是以2为基数的，所以2的幂是完全可以表示的），但对于非2的基数，这将使代码可以移植。
kaveman ：
虽然你对缺失的 return 的看法是正确的，但这个实现仍有一个错误。当你运行 is_power(2) 时会发生什么？
kaveman ：
为什么不直接修改你的实施方案，以免混淆OP和未来的读者？
Manas Chaturvedi ：
是的，我错过了 "返回"。谢谢你指出来!
will ：
你的答案是错误的--请看下面我的答案。在一些数字上试试你的函数，它应该返回错误--即： 5,9,10,11,17,18,19,20,21,22,23,33,34,35,36,37,38,39,40,... 。
Marcus Müller ：
@will., 你是对的。我以为我看到了一个python3.4的标签，但我错了。所以，是的，我将有一个编辑，这将解决这个问题。
will
will
发布于 2020-07-30
0 人赞同

上面提供的答案是 wrong .

是的，它对2的幂有效，但也会产生很多假阳性结果--因为你使用的是整数除法--因为你使用的是python 2.7。

如果你使用 from __future__ import division ，它就会起作用，它改变了 / 的行为。- 但这将改变它在整个程序中的行为，这可能不是你想要的。 

print 33/2 # 16
print 32/2 # 16

然而，使用from __future__ import division，输出会变成正确的（或者至少是更直观的）结果--为了得到原始的整数数学行为，你需要使用//来代替（如在python3中）。


因此，正确的答案将更像这样。


def is_power(n):
    n = n/2.0
    if n == 2:
        return True
    elif n > 2:
        return is_power(n)
    else:
        return False

Note the n= n/2.0在开始的时候。


你需要测试你的代码在几个测试案例上的工作情况，而不仅仅是那些你想要特定结果的案例。


另外，我还会选择这样的方式。


def is_power(n):
  if n == 2:
    return True
  elif n%2 != 0:
    return False
  else:
    return is_power(n/2.0)
Marcus Müller ：
很好的答案，绝对是比OPs更好的方法，所以很值得投上一票:)唯一的问题是，当使用 % 运算符时，我们不妨直接使用位数比较运算符，并使用一步法。 return not (n & (n-1)) 。python的好处是它对 "无限大的整数 "有一个有效的实现，所以这甚至适用于非常大的数值（例如： 2**100 -1 ）。
will ：
@MarcusMüller 我不同意将其全部纳入 n&(n-1) 的结构中--除非你将详细的评论与它一起放入，详细说明发生了什么。
Rahul Madhavan
Rahul Madhavan
发布于 2020-07-30
0 人赞同

虽然这没有直接回答你的问题，但实现这一目标的最快方法是 

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

虽然马库斯在之前的文章中已经谈到了这个问题，但再多解释一下可能对一些人有帮助。每个数字的二进制表示和（数字-1）至少共享一个1比特，除非该数字是2的幂。此外，所有的负数都共享前导位，所以被这种方法排除在外。


唯一的例外是数字0，它与前面的数字-1不共享位，可能不会被看作是2的幂，因此这需要一个明确的检查。


数字的二进制表会让人明白这一点。


> Dcml  Binary 5bit
> -15   10001
> -14   10010
> -13   10011
> -12   10100
> -11   10101
> -10   10110
> -9    10111
> -8    11000
> -7    11001
> -6    11010
> -5    11011
> -4    11100
> -3    11101
> -2    11110
> -1    11111 
>  0    00000 
>  1    00001
>  2    00010
>  3    00011
>  4    00100
>  5    00101
>  6    00110
>  7    00111
>  8    01000
>  9    01001
>  10   01010
>  11   01011
>  12   01100
>  13   01101
>  14   01110
>  15   01111
>  16   10000

No negative numbers in this signed number notation would satisfy the condition as they all share the most significant bit as 1. number 0 would satisfy the condition as 0&(any_other_number) == 0. If you need to implement this for very large numbers you may be better off using 位阵列或改变了dtype的numpy。还有。this讨论可能对大数组/数字的位操作速度有帮助。
Hillol Sarker
Hillol Sarker
发布于 2020-07-30
0 人赞同
Power check if a number is a power of 2 Negative numbers are not allowed import math def is_power_of_two(num): :type num: integer x = math.log10(num)/math.log10(2) return 2 ** x == num except ValueError: exit()
Wariored
Wariored
发布于 2020-07-30
0 人赞同

你可以直接使用 数学 图书馆 

import math
def isPowerOfTwo(n):
    if n <= 0:
        return False
    res = int(math.log(n) / math.log(2))
    return 2 ** res == n
Asingwire Cuthbert
Asingwire Cuthbert
发布于 2020-07-30
0 人赞同

这是我对一个检查哪个数字是另一个数字的基数的函数的解决方案。 

def is_power_of(number, base):
  # when number is smaller than base.
  if base <= 1:
    return False
  elif number < base:
    return False
  elif  number > base:
    # keep dividing number by base.
    return is_power_of(number/base, base)
  else:
    return True
Mohideen bin Mohammed
Mohideen bin Mohammed
发布于 2020-07-30
0 人赞同

这将是一点信息。 

counter = 0
def powoftwo(n):
    global counter
    counter+=1
    if n%2 != 0:
      return "Given Number %s is not Power of 2!"%g
    else:      
      if n==2:
        return "yes give number %s = 2**%s is power of 2!"%(g, counter)
      return powoftwo(n/2)
g = 1024
print powoftwo(g)
yes give number 1024 = 2**10 is power of 2!
SeF
SeF
发布于 2020-07-30
0 人赞同

虽然迟到了，但另一种方式。 

import math
 
推荐文章
迷茫的火龙果  ·  boost::any浅析 - 明明1109 - 博客园
3 月前
有情有义的馒头  ·  Matplotlib绘图双纵坐标轴设置及控制设置时间格式-51CTO.COM
1 年前
苦恼的跑步机  ·  连接到 SAP - Azure Logic Apps | Microsoft Learn
1 年前
英姿勃勃的松鼠  ·  HTML CSS笔记文本效果-渐变效果-边框图片效果_8808968的技术博客_51CTO博客
1 年前
善良的牙膏  ·  测试开发之网络篇-常用命令_ITPUB博客
1 年前
今天看啥   ·   Py中国   ·   codingpro   ·   藏经阁   ·   小百科   ·   link之家   ·   卧龙AI搜索
删除内容请联系邮箱 2879853325@qq.com
link之家 - 链接快照平台
© 2024 ~ 沪ICP备11025650号