Znajdź najmniejszą potęgę 2 większą niż n w Pythonie

Question

Jaka jest najprostsza funkcja zwracania najmniejszej potęgi 2, która jest większa lub równa danej nieujemnej liczbie całkowitej w Pythonie?

Na przykład najmniejsza siła 2 większe lub równe 6 wynosi 8.

Answer 1

Test Spójrzmy prawdzie w oczy:

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) 

Powodem Używam range(1, 1000001) zamiast tylko range(1000000) jest to, że wersja power_log zawiedzie na 0. Powodem, dla którego używam małej liczby powtórzeń w szerokim zakresie zamiast wielu powtórzeń w małym zakresie, jest to, że oczekuję, że różne wersje będą miały różną wydajność w różnych domenach. (Jeżeli spodziewają się nazywając to z ogromnymi liczbami tysiąc-bitowych, oczywiście, chcesz testu, który używa tych).

z jabłkiem Python 2.7.2:

4.38817000389: power_bit_length 
3.69475698471: shift_bit_length 
7.91623902321: power_log 

Z Python.org Pythonie 3.3.0:

6.566169916652143: power_bit_length 
3.098236607853323: shift_bit_length 
9.982460380066186: power_log 

Z pypy 1.9.0/2.7.2:

2.8580930233: power_bit_length 
2.49524712563: shift_bit_length 
3.4371240139: power_log 

wierzę, że to pokazuje, że 2** to powolna część; używanie bit_length zamiast log przyspiesza działanie, ale ważniejsze jest używanie 1<< zamiast 2**.

Sądzę, że jest jaśniejszy. Wersja OP wymaga mentalnego przełączenia kontekstu z logarytmów na bity, a następnie z powrotem do wykładników. Pozostań w bitach przez cały czas (shift_bit_length) lub pozostań w dziennikach i wykładnikach (power_log).

Answer 2

zawsze zwraca 2**(x - 1).bit_length() jest nieprawidłowe, ponieważ chociaż zwraca 1 dla x = 1, to zwraca niemonotoniczny 2 dla x = 0. Prosty fix to monotonicznie bezpieczny dla x = 0:

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

Przykładowe wyjścia:

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

Może pedantycznie argumentować, że x = 0 powinien powrócić 0 (a nie 1), ponieważ 2**float('-inf') == 0 .

Answer 3

będzie to praca dla Ciebie:

import math 

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

Zauważ, że math.log2 jest dostępny w Pythonie 3, ale nie w Pythonie 2. Używanie go zamiast math.log unika problemów numerycznych z nią w 2 ** 29 i poza nią.

Przykładowe wyniki:

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

pedantycznie Można uznać, że x = 0, należy zwrócić 0 (1), a nie, jako 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++; 

Dla 16-bitowej liczby całkowitej.

Answer 5

Możemy to zrobić w następujący wiertłem manipulacji: wyjścia

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 

Próbka:

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

Dla dalszego czytania, patrz this resource.