BitArrayの最終セットビットを取得するには？

Question

BitArrayの最終セットビットを取得するのに有効な（高速）方法は何ですか？ （LINQまたは単純な逆ループは大規模なビットマップではあまり速くないので速くする必要があります）BitArray 次のアルゴリズムを参照してください：BitArrayの内部int配列データを元に戻し、コンパイラを使用する組み込み関数C++のように_BitScanReverse C＃で）。

Answer 1

"正常な" 解決策：

static long FindLastSetBit(BitArray array) 
    { 
     for (int i = array.Length - 1; i >= 0; i--) 
     { 
      if (array[i]) 
      { 
       return i; 
      } 
     } 

     return -1; 
    } 

反射溶液（ノート - BitArrayの実装に依存しています）：

static long FindLastSetBitReflection(BitArray array) 
    { 
     int[] intArray = (int[])array.GetType().GetField("m_array", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(array); 

     for (var i = intArray.Length - 1; i >= 0; i--) 
     { 
      var b = intArray[i]; 
      if (b != 0) 
      { 
       var pos = (i << 5) + 31; 
       for (int bit = 31; bit >= 0; bit--) 
       { 
        if ((b & (1 << bit)) != 0) 
         return pos; 

        pos--; 
       } 

       return pos; 
      } 
     } 

     return -1; 
    } 

反射ソリューションは、大規模なBitArrayに私のため50-100x高速であります非常に小さなものでは、反射のオーバーヘッドが現れ始めます。私のマシンでは1メガバイトあたり約0.2msかかります。

主なことは、if (b != 0)が一度に32ビットをチェックすることです。特定のビットをチェックする内部ループは、正しい単語が見つかったときに1回だけ実行されます。

編集済み：安全性の低いコードは、ほとんど何も得られなかったために削除されました。配列の境界チェックだけが回避され、コードはすでに非常に速いので、それほど重要ではありません。記録のために、危険な溶液（〜30％速く私のために）：

static unsafe long FindLastSetBitUnsafe(BitArray array) 
    { 
     int[] intArray = (int[])array.GetType().GetField("m_array", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(array); 

     fixed (int* buffer = intArray) 
     { 
      for (var i = intArray.Length - 1; i >= 0; i--) 
      { 
       var b = buffer[i]; 
       if (b != 0) 
       { 
        var pos = (i << 5) + 31; 
        for (int bit = 31; bit >= 0; bit--) 
        { 
         if ((b & (1 << bit)) != 0) 
          return pos; 

         pos--; 
        } 

        return pos; 
       } 
      } 
     } 

     return -1; 
    } 

Answer 2

は、あなたがその最後のセットビットのインデックスをしたい場合は、C＃でこれを行うことができます6.

int? index = array.Select((b,i)=>{Index = i, Value = b}) 
        .LastOrDefault(x => x.Value) 
        ?.Index; 

そうしないと、この

var last = array.Select((b,i)=>{Index = i, Value = b}) 
        .LastOrDefault(x => x.Value); 
int? index = last == null ? (int?)null : last.Index; 

ようindexがされるいずれかの方法を何かをしなければなりませんnullすべてのビットがゼロの場合。

Answer 3

最後から最初のビットまで繰り返す以外に何かできるとは思っていません。設定されていれば、それぞれを尋ねます。

BitArray bits = ...; 
int lastSet = Enumerable.Range(1, bits.Length) 
        .Select(i => bits.Length - i) 
        .Where(i => bits[i]) 
        .DefaultIfEmpty(-1) 
        .First(); 

最後のビットが返されます。存在しない場合は-1、そうでない場合は-1が返されます。自分でテストしていないので、調整が必要な場合があります。

希望します。