在 Python 中查找大于或等于 n 的 2 的最小幂
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14267555/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the smallest power of 2 greater than or equal to n in Python
提问by jhoyla
What is the simplest function to return the smallest power of 2 that is greater than or equal to a given non-negative integer in Python?
在 Python 中返回大于或等于给定非负整数的 2 的最小幂的最简单函数是什么？
For example, the smallest power of 2 greater than or equal to 6 is 8.
例如，大于或等于 6 的 2 的最小幂是 8。
采纳答案by abarnert
Let's test it:
让我们测试一下：
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)
The reason I'm using range(1, 1000001)instead of just range(1000000)is that the power_logversion will fail on 0. The reason I'm using a small number of reps over a largeish range instead of lots of reps over a small range is because I expect that different versions will have different performance over different domains. (If you expect to be calling this with huge thousand-bit numbers, of course, you want a test that uses those.)
我使用range(1, 1000001)而不是仅仅使用的原因range(1000000)是power_log版本将失败0。我在大范围内使用少量代表而不是在小范围内使用大量代表的原因是因为我希望不同的版本在不同的领域有不同的表现。（如果您希望使用巨大的千位数字调用它，当然，您需要使用这些数字的测试。）
With Apple Python 2.7.2:
使用 Apple Python 2.7.2：
4.38817000389: power_bit_length
3.69475698471: shift_bit_length
7.91623902321: power_log
With Python.org Python 3.3.0:
使用 Python.org Python 3.3.0：
6.566169916652143: power_bit_length
3.098236607853323: shift_bit_length
9.982460380066186: power_log
With pypy 1.9.0/2.7.2:
使用 pypy 1.9.0/2.7.2：
2.8580930233: power_bit_length
2.49524712563: shift_bit_length
3.4371240139: power_log
I believe this demonstrates that the 2**is the slow part here; using bit_lengthinstead of logdoes speed things up, but using 1<<instead of 2**is more important.
我相信这表明这2**是这里的缓慢部分；使用bit_length而不是log加快速度，但使用1<<而不是2**更重要。
Also, I think it's clearer. The OP's version requires you to make a mental context-switch from logarithms to bits, and then back to exponents. Either stay in bits the whole time (shift_bit_length), or stay in logs and exponents (power_log).
另外，我认为它更清楚。OP 的版本要求您进行从对数到位的心理上下文切换，然后再回到指数。要么一直保持位（shift_bit_length），要么保持对数和指数（power_log）。
回答by jhoyla
Always returning 2**(x - 1).bit_length()is incorrect because although it returns 1 for x=1, it returns a non-monotonic 2 for x=0. A simple fix that is monotonically safe for x=0 is:
总是返回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()
Sample outputs:
示例输出：
>>> 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
It can pedantically be argued that x=0 should return 0 (and not 1), since 2**float('-inf') == 0.
可以迂腐地认为 x=0 应该返回 0（而不是 1），因为2**float('-inf') == 0.
回答by inspectorG4dget
Would this work for you:
这对你有用吗：
import math
def next_power_of_2(x):
return 1 if x == 0 else 2**math.ceil(math.log2(x))
Note that math.log2is available in Python 3 but not in Python 2. Using it instead of math.logavoids numerical problems with the latter at 2**29 and beyond.
请注意，math.log2它在 Python 3 中可用，但在 Python 2 中不可用。使用它而不是math.log避免后者在 2**29 及以后的数值问题。
Sample outputs:
示例输出：
>>> 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
It can pedantically be argued that x=0 should return 0 (and not 1), since 2**float('-inf') == 0.
可以迂腐地认为 x=0 应该返回 0（而不是 1），因为2**float('-inf') == 0.
回答by sudeepdino008
v+=(v==0);
v--;
v|=v>>1;
v|=v>>2;
v|=v>>4;
v|=v>>8;
v|=v>>16;
v++;
For a 16-bit integer.
对于 16 位整数。
回答by Akash Kandpal
We can do this as follows using bit manipulation:
我们可以使用位操作按如下方式执行此操作：
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
Sample outputs:
示例输出：
>>> 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
For further reading, refer to this resource.
如需进一步阅读，请参阅此资源。
