Trova la potenza minima di 2 maggiore di n in Python

Question

Qual è la funzione più semplice per restituire la più piccola potenza di 2 che è maggiore o uguale a un dato intero non negativo in Python?

Ad esempio, la più piccola potenza di 2 maggiore o uguale a 6 è 8.

Answer 1

prova Ammettiamolo:

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) 

La ragione per cui sto usando range(1, 1000001) invece di range(1000000) è che la versione power_log avrà esito negativo su 0. La ragione per cui sto usando un piccolo numero di ripetizioni su un intervallo più ampio invece di un sacco di ripetizioni su un piccolo intervallo è perché mi aspetto che versioni diverse avranno prestazioni diverse su domini diversi. (Se vi aspettate di essere chiamata tale, con un gran numero mille bit, naturalmente, si desidera un test che utilizza quelli.)

con Apple Python 2.7.2:

4.38817000389: power_bit_length 
3.69475698471: shift_bit_length 
7.91623902321: power_log 

Con Python.org Python 3.3.0:

6.566169916652143: power_bit_length 
3.098236607853323: shift_bit_length 
9.982460380066186: power_log 

Con PyPy 1.9.0/2.7.2:

2.8580930233: power_bit_length 
2.49524712563: shift_bit_length 
3.4371240139: power_log 

credo che questo dimostra che il 012.è la parte lenta qui; utilizzando bit_length invece di log si velocizzano le cose, ma l'utilizzo di 1<< invece di 2** è più importante.

Inoltre, penso che sia più chiaro. La versione dell'OP richiede di creare un contesto mentale: passare dai logaritmi ai bit e quindi tornare agli esponenti. Restare in bit per tutto il tempo (shift_bit_length) o rimanere nei registri e negli esponenti (power_log).

Answer 2

ritorno sempre 2**(x - 1).bit_length() è corretto perché anche se restituisce 1 per x = 1, restituisce un non-monotona 2 per x = 0. Una semplice correzione che è monotona sicuro per x = 0 è:

def next_power_of_2(x): 
    return 1 if x == 0 else 2**(x - 1).bit_length() 

uscite campione:

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

Può pedantemente sostenere che x = 0 dovrebbe restituire 0 (e non 1), dal momento che 2**float('-inf') == 0 .

Answer 3

Sarebbe questo lavoro per voi:

import math 

def next_power_of_2(x): 
    return 1 if x == 0 else 2**math.ceil(math.log2(x)) 

noti che math.log2 è disponibile in Python 3, ma non in Python 2. Utilizzando invece di math.log evita problemi numerici con questi ultimi a 2 ** 29 e oltre.

uscite campione:

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

Può pedantically sostenere che x = 0 restituisce il valore 0 (e non 1), dal 2**float('-inf') == 0.

Answer 4

v+=(v==0); 
v--; 
v|=v>>1; 
v|=v>>2; 
v|=v>>4; 
v|=v>>8; 
v|=v>>16; 
v++; 

Per un numero intero a 16 bit.

Answer 5

Possiamo farlo come segue usando manipolazione bit: uscite

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 

Esempi:

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

Per approfondimenti, consultare this resource.