在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)中.

Answer 2

总是返回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.

Answer 3

这对你有用吗:

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.