15

与えられたに対して、次のようなx < 10^15最大整数を迅速かつ正確に決定します。p2^p <= x

ここに私が試したいくつかのことがあります：

最初にこれを試しましたが、多数の場合は正確ではありません:

>>> from math import log
>>> x = 2**3
>>> x
8
>>> p = int(log(x, 2))
>>> 2**p == x
True
>>> x = 2**50
>>> p = int(log(x, 2))
>>> 2**p == x #not accurate for large numbers?
False

次のようなものを試すことができます：

p = 1
i = 1
while True:
    if i * 2 > n:
        break
    i *= 2
    p += 1
    not_p = n - p

pが50の場合、最大50回の操作が必要になります

2 のすべてのべき乗を 2^50 まで事前に計算し、二分探索を使用して p を見つけることができます。これには約 log(50) 操作が必要ですが、少し過剰で醜いですか?

C ベースのソリューションについては、次のスレッドを見つけました:高速ログ ベース 2 天井を計算する

しかし、それは少し醜いようで、Pythonに変換する方法が正確にはわかりませんでした.

4

7 に答える 7

34

.bit_length()Python >= 2.7 では、整数のメソッドを使用できます。

def brute(x):
    # determine max p such that 2^p <= x
    p = 0
    while 2**p <= x:
        p += 1
    return p-1

def easy(x):
    return x.bit_length() - 1

を与える

>>> brute(0), brute(2**3-1), brute(2**3)
(-1, 2, 3)
>>> easy(0), easy(2**3-1), easy(2**3)
(-1, 2, 3)
>>> brute(2**50-1), brute(2**50), brute(2**50+1)
(49, 50, 50)
>>> easy(2**50-1), easy(2**50), easy(2**50+1)
(49, 50, 50)
>>> 
>>> all(brute(n) == easy(n) for n in range(10**6))
True
>>> nums = (max(2**x+d, 0) for x in range(200) for d in range(-50, 50))
>>> all(brute(n) == easy(n) for n in nums)
True
于 2012-10-28T02:54:48.523 に答える
3

log2numpyの関数を試すことができます。これは 2^62 までの累乗で機能するようです。

>>> 2**np.log2(2**50) == 2**50
True
>>> 2**np.log2(2**62) == 2**62
True

その上で（少なくとも私にとっては）numpyの内部数値型の制限のために失敗しますが、それはあなたが扱っていると言う範囲のデータを処理します。

于 2012-10-28T02:35:03.680 に答える
2

「大きな数に対して正確ではない」に関して、ここでの課題は、浮動小数点表現が実際に必要なほど正確ではないということです( 49.999999999993 != 50.0)。優れたリファレンスは、「すべてのコンピューター科学者が浮動小数点演算について知っておくべきこと」です。

幸いなことに、C ルーチンの変換は非常に簡単です。

def getpos(value):
    if (value == 0):
        return -1
    pos = 0
    if (value & (value - 1)):
        pos = 1
    if (value & 0xFFFFFFFF00000000):
        pos += 32
        value = value >> 32
    if (value & 0x00000000FFFF0000):
        pos += 16
        value = value >> 16
    if (value & 0x000000000000FF00):
        pos += 8
        value = value >> 8
    if (value & 0x00000000000000F0):
        pos += 4
        value = value >> 4
    if (value & 0x000000000000000C):
        pos += 2
        value = value >> 2
    if (value & 0x0000000000000002):
        pos += 1
        value = value >> 1
    return pos

別の方法として、切り捨てる代わりに、最も近い整数に丸めることができます。

   log(x,2)
=> 49.999999999999993
   round(log(x,2),1)
=> 50.0
于 2012-10-28T02:37:59.297 に答える
2

OSX 10.7上のPython 2.6.5（CPython）で動作します：

>>> x = 2**50
>>> x
1125899906842624L
>>> p = int(log(x,2))
>>> p
50
>>> 2**p == x
True

少なくとも 1e9 までの指数では機能し続けますが、それまでには計算にかなりの時間がかかり始めます。あなたは実際にあなたのテストで何を得ていxますpか？どの OS で、どのバージョンの Python を実行していますか?

于 2012-10-28T02:35:01.547 に答える