Find the smallest power of 2 greater than or equal to n in Python

Question

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?

For example, the smallest power of 2 greater than or equal to 6 is 8.

Answer 1

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

Answer 2

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.