Find the smallest power of 2 greater than or equal to n in Python
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_log
version 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.)
With 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:
6.566169916652143: power_bit_length
3.098236607853323: shift_bit_length
9.982460380066186: power_log
With 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_length
instead of log
does speed things up, but using 1<<
instead of 2**
is more important.
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
).
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:
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
.