Найти наименьшую мощность 2 больше, чем n в Python

Ответ 1

Пусть проверит его:

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)

Причина, по которой я использую range(1, 1000001) вместо всего range(1000000) заключается в том, что версия power_log завершится с ошибкой на 0. Причина, по которой я использую небольшое количество повторений в большом диапазоне, а не много повторений в небольшом диапазоне, заключается в том, что я ожидаю, что разные версии будут иметь разную производительность в разных доменах. (Если вы ожидаете, что будете называть это огромными тысячами бит, конечно, вам нужен тест, который их использует.)

С Apple Python 2.7.2:

4.38817000389: power_bit_length
3.69475698471: shift_bit_length
7.91623902321: power_log

С Python.org Python 3.3.0:

6.566169916652143: power_bit_length
3.098236607853323: shift_bit_length
9.982460380066186: power_log

С pypy 1.9.0/2.7.2:

2.8580930233: power_bit_length
2.49524712563: shift_bit_length
3.4371240139: power_log

Я считаю, что это показывает, что 2** - это медленная часть здесь; использование bit_length вместо log действительно ускоряет работу, но более важно использовать 1<< вместо 2**.

Кроме того, я думаю, это яснее. Версия OP требует, чтобы вы сделали ментальный контекст-переключатель из логарифмов в биты, а затем обратно к показателям. Оставайтесь в битах все время (shift_bit_length) или оставайтесь в журналах и экспонентах (power_log).

Ответ 2

Всегда возвращать 2**(x - 1).bit_length() неверно, потому что, хотя он возвращает 1 для x = 1, он возвращает немонотонную 2 для x = 0. Простое исправление, монотонно безопасное для x = 0:

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

Примеры выходов:

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

Можно утверждать, что x = 0 должен возвращать 0 (а не 1), так как 2**float('-inf') == 0.

Ответ 3

Будет ли это работать для вас:

import math

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

Обратите внимание: math.log2 доступен в Python 3, но не в Python 2. Использование вместо math.log позволяет избежать числовых проблем с последним при 2 ** 29 и выше.

Примеры выходов:

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

Можно утверждать, что x = 0 должен возвращать 0 (а не 1), так как 2**float('-inf') == 0.

Ответ 4

Мы можем сделать это следующим образом, используя бит-манипуляцию:

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

Примеры выходов:

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

Для дальнейшего чтения обратитесь к этому ресурсу.

Ответ 5

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

Для 16-разрядного целого.