Как получить последний бит бит в BitArray?

Question

Что такое эффективный (быстрый) способ получить последний бит бит в BitArray. (LINQ или простой обратный цикл не очень быстрый для больших растровых изображений. И мне нужно быстро) BitArray Я вижу следующий алгоритм: вернитесь через внутренние данные массива BitArray и используйте некоторый компилятор Intrinsic Like 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; 
    } 

Решения отражения 50-100x быстрее для меня на большом BitArray s (на очень маленьких будут появляться накладные расходы отражения). Это занимает около 0,2 мс на мегабайт на моей машине.

Главное, что if (b != 0) проверяет сразу 32 бита. Внутренний цикл, который проверяет определенные биты, выполняется только один раз, когда найдено правильное слово.

Отредактировано: небезопасный код удален, потому что я понял, что он ничего не получил, он избегает проверки границы массива, и поскольку код настолько быстр, это уже не так важно. Для записи, небезопасное решение (~ 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, если таковой нет. Не проверял сам, так что это может потребовать некоторой корректировки.

Надеюсь, это поможет.