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

import numpy as np

#A: A random number which may not be a power of two.
#B: The next power of two after A.

B=int(2**np.ceil(np.log2(A)))

if np.log2(B)-1==np.log2(A): B=A

Answer 2

Python provides the frexp() and ldexp() functions in its standard math library. These functions are borrowed from C. Chances are, these methods invoke special hardware instructions (such as converting integers to floating point and extracting the exponent bits from the IEEE 754 floating point format together with the fraction bits).

General version

I could not think about a more efficient method for the general case of obtaining the next power of 2 in Python than using both in combination.

def next_power_of_2(number: float) -> float:
    (fraction, exponent) = math.frexp(number)
    return math.ldexp(1, exponent - (fraction == 0.5))

The fraction == 0.5 part is required because the OP asked for not obtaining the next power of two if the input number is already a power of two.

This function ignores the sign of the argument. And to be honest, the logarithm of a negative integer is usually not defined even with complex numbers, because both or are plausible definitions.

Integer version

If you know that your number is greater than 0.5, the ldexp can be replaced with a faster bit shift. Values less equal than 0.5 will raise a ValueError. (Beware, the result could exceed 64 bits.)

def next_power_of_2(number: float) -> int:
    (fraction, exponent) = math.frexp(number)
    return 1 << (exponent - (fraction == 0.5))

This second version is useful when working with positive integer buffer sizes for algorithms (such as the FFT) which work best with a power of 2 as buffer size.

Answer 3

Hmm, I know this question is old and my answer is pretty simple, but I am really surprised in all this time nobody posted it here, so I will post it as an answer.

The easiest solution is really simple, no need to import any library, you can do it in one loop if you use while statement!

So the logic is very simple, create a variable with a value of 1, while the value of the variable is less than the number, multiply the variable by 2!

Code:

i = 1
while i < n: i *=2

The return values for n = 1, 63, 64, 255, 256, 1000, 4095:

2, 64, 64, 256, 256, 1024, 4096

This can be easily modified to calculate the next power closest to a number of other bases as well:

def nextpower(num, base):
  i = 1
  while i < num: i *= base
  return i

Answer 4

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.log2 is available in Python 3 but not in Python 2. Using it instead of math.log avoids numerical problems with the latter at 2**29 and beyond.

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.

Answer 5

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.

Answer 6

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.

Answer 7

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 8

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.