python - Python で n 以上の最小の 2 のべき乗を見つける

Question

Python で与えられた負でない整数以上の最小の 2 乗を返す最も簡単な関数は何ですか?

たとえば、6 以上の最小の 2 の累乗は 8 です。

Answer 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)just の代わりに使用している理由range(1000000)は、power_logバージョンが で失敗するため0です。狭い範囲で多数の担当者を使用するのではなく、広い範囲で少数の担当者を使用している理由は、バージョンが異なればドメインが異なればパフォーマンスも異なると予想されるためです。(もちろん、1000 ビットの膨大な数でこれを呼び出すことが予想される場合は、それらを使用するテストが必要です。)

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

Answer 2

2**(x - 1).bit_length()x=1 の場合は 1 を返しますが、x=0 の場合は非単調な 2 を返すため、常に返すのは正しくありません。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 は (1 ではなく) 0 を返すべきであると、辛辣に論じることができます2**float('-inf') == 0。

Answer 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 は (1 ではなく) 0 を返すべきであると、辛辣に論じることができます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++;

16 ビット整数の場合。