-1

这是一道面试题：

  1. 编写一个接受整数作为参数并返回布尔值的函数。如果整数是 2 的指数（幂），则返回的布尔值为真，否则为假。一个。没有数学库或按位运算，只有 + - * / % b。1 是二的零次方。C。没有花车，所以没有“负面力量”。d。通常应该比权力更快地识别非权力。e. 任何语言，尽管与所需位置的一般重叠都是明智的。

我对布尔值真的很粗鲁，因为我一年左右没有上过我的 Java 课，所以任何帮助或想法都将不胜感激。

4

5 回答 5

4

满足所有 4 个要求的最佳方法是继续减半n，直到奇数或 1。

def ispow(n):
    while True:
        if n == 1:
            return True
        if n % 2 == 1:
            return False
        n = n / 2

输出：

1 True
2 True
3 False
4 True
5 False
6 False
7 False
8 True
9 False
10 False
于 2012-11-20T02:09:17.693 回答
2

蒂姆的答案显然是面试官正在寻找的答案。

但是，您可以通过打破规则做得更好：

d。通常应该比权力更快地识别非权力。

正如 BoppreH 指出的那样，向上计数而不是向下计数的答案会更快（至少对于大多数语言和平台而言），因为没有除法。在最坏的情况下，他的实现比 Tim 快了近一个数量级。

当然 BoppreH 的平均情况和最佳情况与最坏情况基本相同，而在 Tim 的最好情况下要好得多。但通常最坏的情况是非常重要的，所以这当然是一个值得研究的权衡。

或者：

一个。没有数学库或按位运算，只有 + - * / %

Tim 解决方案的缓慢部分是除法运算符，但实际上，它们不是必需的。你可以用 和 替换n % 2 == 1，n & 1它们n = n / 2保证n = n >> 1是等价的，突然之间，最坏的情况是快一个数量级——甚至比 BoppreH 的还要快。

这是你可能期望编译器在 C 语言中为你做的事情（然后再次尝试2**100000在 C 语言中不使用数学库来处理......），但在 Python 中（至少 CPython——它可能值得尝试 PyPy，并且也许是 Jython 和 IronPython），你必须手动完成。你应该被允许。

这就是为什么这类面试问题是愚蠢和毫无意义的，除了作为进一步讨论的起点。他们显然在寻找的答案通常不是您想要在实际代码中使用的答案。

于 2012-11-20T02:41:32.397 回答
1

更短，每次迭代只执行一次乘法。

def is_power(x):
    current_power = 1
    while current_power < x:
        current_power *= 2
    return current_power == x

x = 2 ^ 100.000 的基准

number = str(2 ** 100000)
cProfile.run('is_power(' + number + ')')
cProfile.run('ispow(' + number + ')')
cProfile.run('is_pow_2(' + number + ')')

  • is_power (this): 1.264 秒

  • ispow（蒂姆的回答）：11.455 秒

另一个还没写完……

于 2012-11-20T02:15:28.310 回答
0

怎么样

import re
n = 2**5
print   bool(re.match("^10*$",bin(n)[2:]))
于 2012-11-20T04:43:17.990 回答
0

当一切都失败时，使用武力：

def is_pow_2(x):
    i=0
    while 2**i <= x:
        if x == 2**i:
           return True
        i += 1
    return False
于 2012-11-20T02:07:40.297 回答