python - 在Python中找到大于或等于n的2的最小幂

Question

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

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

Answer 1

让我们测试一下:

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_log版本将在 0 上失败.我在较大范围内使用少量代表而不是在小范围内使用大量代表的原因是因为我希望不同的版本在不同的域上具有不同的性能。 (当然，如果您希望使用巨大的千位数来调用它，那么您需要一个使用这些的测试。)

使用 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)。