ビット演算のみを使用して2の累乗から指数を抽出する簡単な方法はありますか？
編集：質問はもともとビット演算に関するものでしたが、 「 PythonでY = 2 Xの場合にXを見つける最も速い方法は何ですか？」**
私は現在、フォームの偶数Nを減らすルーチン（ Rabin-Miller素数性テスト）を最適化しようとしています。私は次の方法で部品を入手できます：2**s * d2**s
two_power_s = N & -N
しかし、ビット演算で「 s 」だけを抽出する方法が見つかりません。私が現在あまり満足せずにテストしている回避策（それらはすべてかなり遅いです）は次のとおりです。
私はPythonを使用していますが、この質問に対する答えは言語に依存しないはずです。
「言語にとらわれない」こととパフォーマンスを心配することは、ほとんど互換性のない概念です。
最近のほとんどのプロセッサには、「先行ゼロをカウントする」というCLZ命令があります。GCCでは、__ builtin_clz（x）を使用してこれに到達できます（これにより、clzがないターゲットに対して、最速ではないにしても、妥当なコードも生成されます）。このCLZはゼロに対して未定義であるため、アプリケーションで重要な場合は、そのケースをキャッチするために追加のブランチが必要になることに注意してください。
CELT（http://celt-codec.org）では、CLZがないコンパイラに使用するブランチレスCLZは、TimothyB.Terriberryによって作成されました。
int ilog(uint32 _v){
int ret;
int m;
ret=!!_v;
m=!!(_v&0xFFFF0000)<<4;
_v>>=m;
ret|=m;
m=!!(_v&0xFF00)<<3;
_v>>=m;
ret|=m;
m=!!(_v&0xF0)<<2;
_v>>=m;
ret|=m;
m=!!(_v&0xC)<<1;
_v>>=m;
ret|=m;
ret+=!!(_v&0x2);
return ret;
}
（コメントは、これが分岐バージョンおよびルックアップテーブルベースのバージョンよりも高速であることがわかったことを示しています）
ただし、パフォーマンスがそれほど重要な場合は、コードのこの部分をPythonで実装するべきではありません。
Pythonに関する限り：
timeit.Timer.repeat(testn, cycles)場所を介して取得され、秒の範囲の時間を取得するようにスクリプトによって自動的に調整されました（注：この自動調整メカニズムにはバグがあり、18/02/に修正されました。 2010）。testncyclesfunc（2 5）**
hashlookup: 0.13s 100%
lookup: 0.15s 109%
stringcount: 0.29s 220%
unrolled_bitwise: 0.36s 272%
log_e: 0.60s 450%
bitcounter: 0.64s 479%
log_2: 0.69s 515%
ilog: 0.81s 609%
bitwise: 1.10s 821%
olgn: 1.42s 1065%
func（2 31）**
hashlookup: 0.11s 100%
unrolled_bitwise: 0.26s 229%
log_e: 0.30s 268%
stringcount: 0.30s 270%
log_2: 0.34s 301%
ilog: 0.41s 363%
bitwise: 0.87s 778%
olgn: 1.02s 912%
bitcounter: 1.42s 1264%
func（2 128）**
hashlookup: 0.01s 100%
stringcount: 0.03s 264%
log_e: 0.04s 315%
log_2: 0.04s 383%
olgn: 0.18s 1585%
bitcounter: 1.41s 12393%
func（2 1024）**
log_e: 0.00s 100%
log_2: 0.01s 118%
stringcount: 0.02s 354%
olgn: 0.03s 707%
bitcounter: 1.73s 37695%
import math, sys
def stringcount(v):
"""mac"""
return len(bin(v)) - 3
def log_2(v):
"""mac"""
return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999
def log_e(v):
"""bp on mac"""
return int(round(math.log(v)/0.69314718055994529, 0)) # 0.69 == log(2)
def bitcounter(v):
"""John Y on mac"""
r = 0
while v > 1 :
v >>= 1
r += 1
return r
def olgn(n) :
"""outis"""
if n < 1:
return -1
low = 0
high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
def hashlookup(v):
"""mac on brone -- limit: v < 2**131"""
# def prepareTable(max_log2=130) :
# hash_table = {}
# for p in range(1, max_log2) :
# hash_table[2**p] = p
# return hash_table
global hash_table
return hash_table[v]
def lookup(v):
"""brone -- limit: v < 2**11"""
# def prepareTable(max_log2=10) :
# log2s_table=[0]*((1<<max_log2)+1)
# for i in range(max_log2+1):
# log2s_table[1<<i]=i
# return tuple(log2s_table)
global log2s_table
return log2s_table[v]
def bitwise(v):
"""Mark Byers -- limit: v < 2**32"""
b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000)
S = (1, 2, 4, 8, 16)
r = 0
for i in range(4, -1, -1) :
if (v & b[i]) :
v >>= S[i];
r |= S[i];
return r
def unrolled_bitwise(v):
"""x4u on Mark Byers -- limit: v < 2**33"""
r = 0;
if v > 0xffff :
v >>= 16
r = 16;
if v > 0x00ff :
v >>= 8
r += 8;
if v > 0x000f :
v >>= 4
r += 4;
if v > 0x0003 :
v >>= 2
r += 2;
return r + (v >> 1)
def ilog(v):
"""Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32"""
ret = 1
m = (not not v & 0xFFFF0000) << 4;
v >>= m;
ret |= m;
m = (not not v & 0xFF00) << 3;
v >>= m;
ret |= m;
m = (not not v & 0xF0) << 2;
v >>= m;
ret |= m;
m = (not not v & 0xC) << 1;
v >>= m;
ret |= m;
ret += (not not v & 0x2);
return ret - 1;
# following table is equal to "return hashlookup.prepareTable()"
hash_table = {...} # numbers have been cut out to avoid cluttering the post
# following table is equal to "return lookup.prepareTable()" - cached for speed
log2s_table = (...) # numbers have been cut out to avoid cluttering the post
これらの種類のトリックやハックがたくさんあるページがあります。これはC用に書かれていますが、それらの多くはPythonでも動作するはずです（ただし、パフォーマンスは明らかに異なります）。あなたが欲しいビットはこことそれ以降です。
たとえば、これを試すことができます。
register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
if (v & b[i])
{
v >>= S[i];
r |= S[i];
}
}
Pythonに簡単に変換できるようです。
binsearchを使用して、任意の長さの整数に対してO（lg s）時間でそれを行うことができます。
import sys
def floorlg(n):
if n < 1:
return -1
low=0
high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
固定サイズの整数の場合、ルックアップテーブルが最速のソリューションであり、おそらく全体的に最適です。
パーティーに遅れましたが、どうint.bit_length(n) - 1ですか？あなたは簡単なことを求めました、そしてそれは私にとって最も簡単なようです。CPythonの実装は適度にパフォーマンスが高いように見えます。
範囲はわかっているようです。もっと面白くするために、1<<20まで上がると仮定しましょう。
max_log2=20
したがって、（事実上）整数を2を底とする対数にマップするリストを作成します。以下はトリックを行います：
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
（これは、2の累乗ではない数値には何の役にも立ちません。問題の説明は、それらを処理する必要がないことを示しています。ただし、それを修正するのは簡単です。）
対数を取得する関数は非常に単純で、簡単にインライン化できます。
def table(v):
return log2s_table[v]
私が書いたテストコードが、サンプルのタイミングを取得するために使用されているものとまったく同じであることを保証することはできませんが、これはstringcountコードよりもかなり高速です。
stringcount: 0.43 s.
table: 0.16 s.
テーブル内のすべての値が256未満であるため、リストの代わりに文字列を使用する方が速いのか、それともarray.arrayバイト単位であるのか疑問に思いましたが、サイコロはありません。
string: 0.25 s.
arr: 0.21 s.
ルックアップを実行するためにを使用するdictことは、2の累乗のみがチェックされる方法を利用して、別の可能性です。
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
ただし、この結果はそれほど良くありませんでした。
map: 0.20 s.
また、楽しみのためhexに、floatオブジェクトのメソッドを使用して、数値の基数2の指数を（最後の部分として）含む文字列を取得することもできます。これは一般的に抽出するのに少し時間がかかりますが、指数が1桁になるだけの場合は、簡単に実行できます。
def floathex(v):
return ord(float(v).hex()[-1])-48
これは、競争力がなかったため、純粋にエンターテインメントの価値のためです。ただし、驚くべきことに、ビット単位のアプローチよりも高速です。
したがって、リストを使用するのが道のりのようです。
（このアプローチはメモリが限られているため、無制限にスケーリングすることはありませんが、それを補うために、実行速度はmax_log2、Pythonコードを実行するときに気付くような方法で、または入力値に依存しません。メモリについて消費量、Pythonの内部を正しく覚えている場合(1<<max_log2)*4、内容はすべて小さな整数であり、インタープリターが自動的にインターンするため、テーブルは約バイトを占有します。したがって、max_log2が20の場合、約4MBになります。）
これは実際にはmacによって投稿されたパフォーマンステストへのコメントです。適切なコードのフォーマットとインデントを行うための回答としてこれを投稿します
mac、Mark Byersによって提案されたbitseachの展開された実装を試してみませんか？多分それを遅くするのはアレイアクセスだけです。理論的には、このアプローチは他のアプローチよりも高速であるはずです。
書式設定がPythonに適しているかどうかはわかりませんが、このようになりますが、それが何をするのかはわかると思います。
def bitwise(v):
r = 0;
if( v > 0xffff ) : v >>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
PythonがJavaの未歌の整数の欠如を共有する場合、次のようにする必要があります。
def bitwise(v):
r = 0;
if( v & 0xffff0000 ) : v >>>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );