Log（）を使用せずにビット位置を見つけよう

Question

私は2の累乗（1,2,4,8など）の整数入力を持っています。私は関数がlog（）を使わずにビット位置を返すようにしたい。たとえば、上記の入力はそれぞれ{0,1,2,3}を返します。これはC＃の場合です。これがSQLで実行できる場合はプラスです。

ありがとうございます！

Answer 1

これを行うために私が見つけた最も速いコードは、Bit Twiddling Hacksサイトからです。具体的には、DeBruijnシーケンスに基づくルックアップ。 http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

私は、単純な方法、スイッチベースの方法、および2つのBit Twiddling Hacksメソッドをテストしました。DeBruijnシーケンスと、「値が2の累乗であることがわかっている場合」の2つです。

これらのすべてを3200万の2の累乗の配列に対して実行しました。すなわち、2^Nという形式の整数で、Nは0..30の範囲にあります。 2^31の値は負の数であり、これは単純なメソッドを無限ループにします。

リリースモードでVisual Studio 2010でコードをコンパイルし、デバッガなしで（Ctrl + F5）実行しました。私のシステムでは、数十以上の平均値は、実行は以下のとおりです。

• ナイーブ方法：950ミリ秒
• スイッチの方法：660ミリ秒
• Bithack方法1：1154ミリ秒
• DeBruijn：105ミリ秒

DeBruijnシーケンス方法は他のどの方法よりもはるかに高速です。他のBithackメソッドは、CからC＃への変換がいくつかの非効率を招くため、ここでは劣っています。たとえば、Cの文int r = (v & b[0]) != 0;は、ifまたはC＃の3進演算子（つまり？:)を必要とします。

ここにコードがあります。

class Program 
{ 
    const int Million = 1000 * 1000; 
    static readonly int NumValues = 32 * Million; 

    static void Main(string[] args) 
    { 
     // Construct a table of integers. 
     // These are random powers of two. 
     // That is 2^N, where N is in the range 0..31. 
     Console.WriteLine("Constructing table"); 
     int[] values = new int[NumValues]; 
     Random rnd = new Random(); 
     for (int i = 0; i < NumValues; ++i) 
     { 
      int pow = rnd.Next(31); 
      values[i] = 1 << pow; 
     } 

     // Run each one once to make sure it's JITted 
     GetLog2_Bithack(values[0]); 
     GetLog2_DeBruijn(values[0]); 
     GetLog2_Switch(values[0]); 
     GetLog2_Naive(values[0]); 

     Stopwatch sw = new Stopwatch(); 
     Console.Write("GetLog2_Naive ... "); 
     sw.Restart(); 
     for (int i = 0; i < NumValues; ++i) 
     { 
      GetLog2_Naive(values[i]); 
     } 
     sw.Stop(); 
     Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds); 

     Console.Write("GetLog2_Switch ... "); 
     sw.Restart(); 
     for (int i = 0; i < NumValues; ++i) 
     { 
      GetLog2_Switch(values[i]); 
     } 
     sw.Stop(); 
     Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds); 

     Console.Write("GetLog2_Bithack ... "); 
     sw.Restart(); 
     for (int i = 0; i < NumValues; ++i) 
     { 
      GetLog2_Bithack(values[i]); 
     } 
     Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds); 

     Console.Write("GetLog2_DeBruijn ... "); 
     sw.Restart(); 
     for (int i = 0; i < NumValues; ++i) 
     { 
      GetLog2_DeBruijn(values[i]); 
     } 
     sw.Stop(); 
     Console.WriteLine("{0:N0} ms", sw.ElapsedMilliseconds); 


     Console.ReadLine(); 
    } 

    static int GetLog2_Naive(int v) 
    { 
     int r = 0; 
     while ((v = v >> 1) != 0) 
     { 
      ++r; 
     } 
     return r; 
    } 

    static readonly int[] MultiplyDeBruijnBitPosition2 = new int[32] 
    { 
     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
    }; 

    static int GetLog2_DeBruijn(int v) 
    { 
     return MultiplyDeBruijnBitPosition2[(uint)(v * 0x077CB531U) >> 27]; 
    } 

    static readonly uint[] b = new uint[] { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000}; 

    static int GetLog2_Bithack(int v) 
    { 
     int r = (v & b[0]) == 0 ? 0 : 1; 
     int x = 1 << 4; 
     for (int i = 4; i > 0; i--) // unroll for speed... 
     { 
      if ((v & b[i]) != 0) 
       r |= x; 
      x >>= 1; 
     } 
     return r; 
    } 

    static int GetLog2_Switch(int v) 
    { 
     switch (v) 
     { 
      case 0x00000001: return 0; 
      case 0x00000002: return 1; 
      case 0x00000004: return 2; 
      case 0x00000008: return 3; 
      case 0x00000010: return 4; 
      case 0x00000020: return 5; 
      case 0x00000040: return 6; 
      case 0x00000080: return 7; 
      case 0x00000100: return 8; 
      case 0x00000200: return 9; 
      case 0x00000400: return 10; 
      case 0x00000800: return 11; 
      case 0x00001000: return 12; 
      case 0x00002000: return 13; 
      case 0x00004000: return 14; 
      case 0x00008000: return 15; 
      case 0x00010000: return 16; 
      case 0x00020000: return 17; 
      case 0x00040000: return 18; 
      case 0x00080000: return 19; 
      case 0x00100000: return 20; 
      case 0x00200000: return 21; 
      case 0x00400000: return 22; 
      case 0x00800000: return 23; 
      case 0x01000000: return 24; 
      case 0x02000000: return 25; 
      case 0x04000000: return 26; 
      case 0x08000000: return 27; 
      case 0x10000000: return 28; 
      case 0x20000000: return 29; 
      case 0x40000000: return 30; 
      case int.MinValue: return 31; 
      default: 
       return -1; 
     } 
    } 
} 

Iがループをアンロールし、代わりにアレイのルックアップの定数を使用してBithackコードを最適化する場合、その時間は、switch文法のための時間と同じです。

static int GetLog2_Bithack(int v) 
{ 
    int r = ((v & 0xAAAAAAAA) != 0) ? 1 : 0; 
    if ((v & 0xFFFF0000) != 0) r |= (1 << 4); 
    if ((v & 0xFF00FF00) != 0) r |= (1 << 3); 
    if ((v & 0xF0F0F0F0) != 0) r |= (1 << 2); 
    if ((v & 0xCCCCCCCC) != 0) r |= (1 << 1); 
    return r; 
} 

Answer 2

私はこれをテストするためにMacにVSを持っていませんが、このようなものが欲しいですか？

public static int Foo(int n) 
{ 
    if (n <= 0) 
    { 
     return -1; // A weird value is better than an infinite loop. 
    } 
    int i = 0; 
    while (n % 2 == 0) 
    { 
     n /= 2; 
     i++; 
    } 

    return i; 
} 

Answer 3

0]数は言語でゼロまたは負、リターン/スローエラー

1]である場合、2

2]塩基に変換ベースに番号を変換する構築物を見つけます-2文字列に値が

3]文字列の長さから1を引い

Answer 4

冗長コードを返す、おそらく最速：

if (x < 1) 
    throw SomeException(); 
if (x < 2) 
    return 0; 
if (x < 4) 
    return 1; 
if (x < 8) 
    return 2; 
//.... etc. 

これには、分割も、二重からの変換も含まれません。非常に速い比較しか必要ありません。議論については、Code Complete, 2nd edition、633ページを参照してください。

あなたが入力が常に2の累乗になることがわかっている場合は、スイッチブロックからより良いパフォーマンスを得る可能性があります：

switch (input) 
{ 
    case 1: 
     return 0; 
    case 2: 
     return 1; 
    case 4: 
     return 2; 
    case 8: 
     return 3; 
    //... 
    default: 
     throw SomeException(); 
} 

を私は千万のランダムなint型のパフォーマンスをテストし、千万のランダム選択された2の累乗。結果：

• Bithacks 1：1360ミリ秒
• Bithacks 2：1103ミリ秒
• 場合：1320ミリ秒
• Bithacks 1（2の累乗）：1335ミリ秒
• Bithacks 2（ （2のべき乗）：1060ミリ秒
• Bithacks 3（2のべき乗）：1286ミリ秒
• If（2の累乗）：1026 mi lliseconds
• スイッチ（2のべき乗）：896ミリ秒

を私は10回で反復回数を増加させ、そしてこれらの結果だ：

• Bithacks 1：13347ミリ秒
• Bithacks 2：10370ミリ秒
• If：12918ミリ秒
• Bithacks 1（2の累乗）：12528ミリ秒
• Bithacks 2（2の累乗）：10150ミリ秒
• Bithacks 3（2の累乗）：12384ミリ秒
• 場合（2の累乗）：9969ミリ秒
• スイッチ（2のべき乗）：8937ミリ秒

今、私はC＃のコードにビットハックを変換するときに愚かな何かをしたかどうかを確認するために任意のプロファイリングをしませんでした、またのどれだけを見て実行時間はログを計算する関数で費やされます。だからこれはちょうど包括的な種類の計算ですが、もしifのアプローチがビットハックアルゴリズムとほぼ同じで、スイッチが少し速いことを示唆しています。さらに、ifとswitchのアプローチは理解して維持するのがはるかに簡単です。

Answer 5

これはそれを行うためのCPUに優しい方法です：

SQLについては

int bitpos=-1; 
while(num>0) { 
    num = num>>1; 
    bitpos++; 
} 
return bitpos; 

、CASEを使用しています。パフォーマンスが問題になる場合は、ネストされたIF....ELSEを使用してバイナリ検索を実行できます。しかし、32の可能な値だけでは、それを実装するオーバーヘッドは、単純なシーケンシャル検索よりはるかに多くなる可能性があります。あなた - Cでコーディングされたパワー・オブ・2バイト（1ビットだけがセットされたUINT8旗）で

Answer 6

検索ビット位置（C＃のことは知らない）

これは、ビット位置1..8を返します。インデクシング0..7の結果を減らす必要があるかもしれない。ここに私のブログ投稿を参照してくださいコードスニペットの "進化" の情報について

int pos(int a){ 
    int p = (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1); 
    return p; 
} 

http://blog.edutoolbox.de/?p=263

EDIT：

deBruijnスタイルを約100倍高速です...