30

返回大于或等于 Python 中给定非负整数的 2 的最小幂的最简单函数是什么？

例如，大于或等于 6 的 2 的最小幂是 8。

4

6 回答 6

44

让我们测试一下：

import collections
import math
import timeit

def power_bit_length(x):
    return 2**(x-1).bit_length()

def shift_bit_length(x):
    return 1<<(x-1).bit_length()

def power_log(x):
    return 2**(math.ceil(math.log(x, 2)))

def test(f):
    collections.deque((f(i) for i in range(1, 1000001)), maxlen=0)

def timetest(f):
    print('{}: {}'.format(timeit.timeit(lambda: test(f), number=10),
                          f.__name__))

timetest(power_bit_length)
timetest(shift_bit_length)
timetest(power_log)

我使用的原因不仅仅是range(1, 1000001)版本将在. 我在较大范围内使用少量代表而不是在小范围内使用大量代表的原因是因为我希望不同的版本在不同的域上具有不同的性能。（当然，如果您希望使用巨大的千位数来调用它，那么您需要一个使用这些的测试。）range(1000000)power_log0

使用 Apple Python 2.7.2：

4.38817000389: power_bit_length
3.69475698471: shift_bit_length
7.91623902321: power_log

使用 Python.org Python 3.3.0：

6.566169916652143: power_bit_length
3.098236607853323: shift_bit_length
9.982460380066186: power_log

使用 pypy 1.9.0/2.7.2：

2.8580930233: power_bit_length
2.49524712563: shift_bit_length
3.4371240139: power_log

我相信这表明这2**是缓慢的部分；使用bit_length代替log确实可以加快速度，但使用1<<代替2**更重要。

另外，我认为它更清楚。OP 的版本要求您从对数到位进行心理上下文切换，然后再返回指数。要么始终保持位 ( shift_bit_length)，要么保持对数和指数 ( power_log)。

于 2013-01-10T21:44:57.483 回答
22

总是返回2**(x - 1).bit_length()是不正确的，因为尽管它为 x=1 返回 1，但它为 x=0 返回一个非单调的 2。对于 x=0 来说单调安全的简单修复是：

def next_power_of_2(x):  
    return 1 if x == 0 else 2**(x - 1).bit_length()

示例输出：

>>> print(', '.join(f'{x}:{next_power_of_2(x)}' for x in range(10)))
0:1, 1:1, 2:2, 3:4, 4:4, 5:8, 6:8, 7:8, 8:8, 9:16

可以迂腐地争论 x=0 应该返回 0（而不是 1），因为2**float('-inf') == 0.

于 2013-01-10T21:26:42.723 回答
13

这对你有用吗：

import math

def next_power_of_2(x):
    return 1 if x == 0 else 2**math.ceil(math.log2(x))

请注意，math.log2它在 Python 3 中可用，但在 Python 2 中不可用。使用它而不是math.log避免后者在 2**29 及以后出现数值问题。

示例输出：

>>> print(', '.join(f'{x}:{next_power_of_2(x)}' for x in range(10)))
0:1, 1:1, 2:2, 3:4, 4:4, 5:8, 6:8, 7:8, 8:8, 9:16

可以迂腐地争论 x=0 应该返回 0（而不是 1），因为2**float('-inf') == 0.

于 2013-01-10T21:33:19.503 回答
3

我们可以使用位操作来做到这一点：

def next_power_of_2(n):
    if n == 0:
        return 1
    if n & (n - 1) == 0:
        return n
    while n & (n - 1) > 0:
        n &= (n - 1)
    return n << 1

示例输出：

>>> print(', '.join(f'{x}:{next_power_of_2(x)}' for x in range(10)))
0:1, 1:1, 2:2, 3:4, 4:4, 5:8, 6:8, 7:8, 8:8, 9:16

如需进一步阅读，请参阅此资源。

于 2018-01-18T13:21:38.883 回答
1 
v+=(v==0);
v--;
v|=v>>1;
v|=v>>2;
v|=v>>4;
v|=v>>8;
v|=v>>16;
v++;

对于 16 位整数。

于 2013-01-12T07:07:07.857 回答
0

嗯，我知道这个问题很老，我的答案很简单，但我真的很惊讶一直没有人在这里发布它，所以我将它作为答案发布。

最简单的解决方案真的很简单，不需要导入任何库，使用while语句就可以一个循环！

所以逻辑很简单，创建一个值为1的变量，而变量的值小于数字，将变量乘以2！

代码：

i = 1
while i < n: i *=2

n = 1、63、64、255、256、1000、4095 的返回值：

2, 64, 64, 256, 256, 1024, 4096

这可以很容易地修改以计算下一个电源柜到许多其他基地：

def nextpower(num, base):
  i = 1
  while i < num: i *= base
  return i
于 2021-05-30T04:39:12.810 回答