ビット演算を使用して n = 2**x の指数を求める [n の 2 を底とする対数]

Question

ビット演算のみを使用して 2 のべき乗から指数を抽出する簡単な方法はありますか?

編集： 質問はもともとビット単位の演算に関するものでしたが、疑問に思っている場合は、このスレッドも読むと良いでしょう。 「Y = 2 の場合に X を見つける最も速い方法は何ですか?バツ Pythonで?"**

現在、ルーチンを最適化しようとしています（ラビン・ミラー素数性検定）を削減します 偶数 フォーム内の N 2**s * d. 。を入手できます 2**s パート：

two_power_s = N & -N

しかし、「」だけを抽出する方法が見つかりませんs" ビット単位の演算を使用します。私が現在テストしている回避策は、あまり満足のいくものではありません (どれも非常に遅いです)。

• 対数関数を使う
• 2** のバイナリ表現を操作します (つまり、末尾のゼロを数えます)
• 結果が 1 になるまで 2 による除算をループします。

私は Python を使用していますが、この質問に対する答えは言語に依存しないはずです。

Answer 1

短い答え

Pythonに関する限り:

• の すべての中で最速の方法 2**x の指数を見つけるには、ハッシュが 2 のべき乗である辞書を調べます (「」を参照)ハッシュルックアップ" コード内)
• の 最速のビット単位の方法 と呼ばれるものですunrolled_bitwise".
• 以前の両方の方法には、明確に定義された (ただし拡張可能な) 上限があります。の ハードコードされた上限のない最速の方法 (Python が数値を処理できる限りスケールアップします) は "log_e".

予備的なメモ

1. 以下のすべての速度測定値は次の方法で取得されました。 timeit.Timer.repeat(testn, cycles) どこ testn 3に設定され、 cycles 秒の範囲の時間を取得するためにスクリプトによって自動的に調整されました (注記： この自動調整メカニズムにはバグがあり、2010 年 2 月 18 日に修正されました)。
2. すべての方法が拡張できるわけではない, 、これが、さまざまな 2 の累乗についてすべての関数をテストしなかった理由です。
3. 提案された方法の一部をうまく機能させることができませんでした (関数は間違った結果を返します)。ステップバイステップのデバッグ セッションを実行するための tiem がまだありませんでした。誰かが検査で間違いを見つけた場合（または自分でデバッグを実行したい場合）に備えて、コードを（コメント化して）含めました。

結果

関数(25)**

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%

関数(231)**

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%

関数(2128)**

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%

関数(21024)**

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

Answer 2

「言語に依存しない」とのパフォーマンスの心配はかなり互換性のない概念です。

最近のほとんどのプロセッサは、「先行ゼロカウント」、CLZ命令を持っています。 GCCでは、__builtin_clz（も合理的な生産、そうでない場合はCLZが不足しているターゲットのための最速、コード）（X）でそれを得ることができます。それはあなたのアプリケーションに重要な場合は、そのケースをキャッチするために、余分な枝が必要になりますので、このCLZがゼロのために定義されていないことに注意してください。

私たちが欠けて示すコンパイラ用に使用し、

CELTで（ http://celt-codec.org の）無店舗のCLZ CLZは、ティモシー・B. 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であなたのコードのこの部分を実装すべきではないということです。

もし

Answer 3

トリックやハックのこれらのタイプの多くのページがあります。これは、Cのために書かれていますが、（パフォーマンスは明らかに異なるだろうが）、それらの多くは、あまりにもPythonで動作するはずです。あなたがしたいビットはここと以降ます。

あなたは例えば、こののnoreferrer">

あなたはOでbinsearchを使用して任意の長さの整数の（LG秒）の時間をそれを行うことができます。

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

は、固定サイズの整数の場合、ルックアップテーブルは最速の解決策であるべきであり、おそらく最高の全体的なています。

範囲が知られているように、

それはそうです。のは、それはそれをより面白くするために、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.

そして、ちょうど楽しみのために1は、（その最後の部分として）数の底2の指数を含んでいる文字列を取得するためにフロートオブジェクトのhexメソッドを使用することができます。これは、一般的に抽出することが少し遅いですが、指数がしか一桁になるだろうされている場合、それは素直に十分に行うことができます：

def floathex(v):
    return ord(float(v).hex()[-1])-48

まだ、驚くほど、ただしビット単位のアプローチよりも速く

- それはuncompetetiveだったとしてのに

これは、エンターテイメントとしての価値のために純粋です。

それはリストを使用してのように見えますが、移動するための方法である。

（このアプローチが原因限られたメモリに、無限に拡張しませんが、Pythonコードを実行するときに、あなたが気づくでしょうどのような方法で、実行速度がmax_log2、または入力値に依存しないことを補うために。私は正しく私のpythonの内部を覚えていれば内容が(1<<max_log2)*4が20であるとき、インタプリタはインターンが自動的に。SO、それは約4MBの意志のすべての小さな整数であるため、メモリの消費量については、表には、max_log2バイト程度かかります。）

これは実際には、MACにより投稿された性能テストにコメントです。私は、適切なコードの書式とを持つように答えとしてこれを投稿インデントの

マック、あなたはマーク・バイヤーズによって提案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 );

unsingned整数の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 );

パーティーに遅れましたが、どうでしょうか int.bit_length(n) - 1?あなたは単純明快な質問をしましたが、私にはそれが最も単純に思えます。CPython 実装はかなりパフォーマンスが高いように見えます。

• 参考資料
• CPython ソースコード

Answer 4

Answer 5

Answer 6

あなたはOでbinsearchを使用して任意の長さの整数の（LG秒）の時間をそれを行うことができます。

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

は、固定サイズの整数の場合、ルックアップテーブルは最速の解決策であるべきであり、おそらく最高の全体的なています。

Answer 7

範囲が知られているように、

それはそうです。のは、それはそれをより面白くするために、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.

そして、ちょうど楽しみのために1は、（その最後の部分として）数の底2の指数を含んでいる文字列を取得するためにフロートオブジェクトのhexメソッドを使用することができます。これは、一般的に抽出することが少し遅いですが、指数がしか一桁になるだろうされている場合、それは素直に十分に行うことができます：

def floathex(v):
    return ord(float(v).hex()[-1])-48

まだ、驚くほど、ただしビット単位のアプローチよりも速く

- それはuncompetetiveだったとしてのに

これは、エンターテイメントとしての価値のために純粋です。

それはリストを使用してのように見えますが、移動するための方法である。

（このアプローチが原因限られたメモリに、無限に拡張しませんが、Pythonコードを実行するときに、あなたが気づくでしょうどのような方法で、実行速度がmax_log2、または入力値に依存しないことを補うために。私は正しく私のpythonの内部を覚えていれば内容が(1<<max_log2)*4が20であるとき、インタプリタはインターンが自動的に。SO、それは約4MBの意志のすべての小さな整数であるため、メモリの消費量については、表には、max_log2バイト程度かかります。）

これは実際には、MACにより投稿された性能テストにコメントです。私は、適切なコードの書式とを持つように答えとしてこれを投稿インデントの

マック、あなたはマーク・バイヤーズによって提案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 );

unsingned整数の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 );

Answer 8

範囲が知られているように、

それはそうです。のは、それはそれをより面白くするために、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.

そして、ちょうど楽しみのために1は、（その最後の部分として）数の底2の指数を含んでいる文字列を取得するためにフロートオブジェクトのhexメソッドを使用することができます。これは、一般的に抽出することが少し遅いですが、指数がしか一桁になるだろうされている場合、それは素直に十分に行うことができます：

def floathex(v):
    return ord(float(v).hex()[-1])-48

まだ、驚くほど、ただしビット単位のアプローチよりも速く

- それはuncompetetiveだったとしてのに

これは、エンターテイメントとしての価値のために純粋です。

それはリストを使用してのように見えますが、移動するための方法である。

（このアプローチが原因限られたメモリに、無限に拡張しませんが、Pythonコードを実行するときに、あなたが気づくでしょうどのような方法で、実行速度がmax_log2、または入力値に依存しないことを補うために。私は正しく私のpythonの内部を覚えていれば内容が(1<<max_log2)*4が20であるとき、インタプリタはインターンが自動的に。SO、それは約4MBの意志のすべての小さな整数であるため、メモリの消費量については、表には、max_log2バイト程度かかります。）

Answer 9

これは実際には、MACにより投稿された性能テストにコメントです。私は、適切なコードの書式とを持つように答えとしてこれを投稿インデントの

マック、あなたはマーク・バイヤーズによって提案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 );

unsingned整数の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 );

Answer 10

パーティーに遅れましたが、どうでしょうか int.bit_length(n) - 1?あなたは単純明快な質問をしましたが、私にはそれが最も単純に思えます。CPython 実装はかなりパフォーマンスが高いように見えます。

• 参考資料
• CPython ソースコード

Answer 11

Answer 12

パーティーに遅れましたが、どうでしょうか int.bit_length(n) - 1?あなたは単純明快な質問をしましたが、私にはそれが最も単純に思えます。CPython 実装はかなりパフォーマンスが高いように見えます。

Answer 13

Answer 14