c# - 有效地比较位( x 的重叠集)

Question

我想将任意长度的比特流与 C# 中的掩码进行比较，并返回相同比特数的比率。要检查的掩码介于 2 位长到 8k 之间(90% 的掩码长 5 位)，输入可以介于 2 位到 ~ 500k 之间，平均输入字符串为 12k(但是，是的，大多数时候它会将 5 位与 12k 的前 5 位进行比较)

现在我天真的实现是这样的:

bool[] mask = new[] { true, true, false, true };
float dendrite(bool[] input) { 
    int correct = 0;
    for ( int i = 0; i<mask.length; i++ ) { 
        if ( input[i] == mask[i] ) 
            correct++;
    }
    return (float)correct/(float)mask.length;
}

但我希望使用某种二元运算符魔法可以更好地处理(更有效)？

有大神指教吗？

编辑:在我的设计中此时数据类型不固定，所以如果 int 或 bytearrays 工作得更好，我也会成为一个快乐的露营者，在这里尝试优化效率，计算越快越好。

例如，如果你能让它像这样工作:

int[] mask = new[] { 1, 1, 0, 1 };
float dendrite(int[] input) { 
    int correct = 0;
    for ( int i = 0; i<mask.length; i++ ) { 
        if ( input[i] == mask[i] ) 
            correct++;
    }
    return (float)correct/(float)mask.length;
}

或者这个:

int mask = 13; //1101
float dendrite(int input) { 

    return // your magic here;
} // would return 0.75 for an input 
  // of 101 given ( 1100101 in binary, 
  // matches 3 bits of the 4 bit mask == .75 

回答:我将每个建议的答案相互比较，Fredou 和 Marten 的解决方案并驾齐驱，但 Fredou 最后提交了最快的最精益实现。当然，由于实现之间的平均结果差异很大，我可能不得不稍后重新访问这篇文章。 :) 但这可能只是我在我的测试脚本中搞砸了。 (我希望，现在太晚了，去 sleep =)

sparse1.Cyclone
1317ms   3467107ticks 10000iterations
result:    0,7851563

sparse1.Marten
288ms   759362ticks 10000iterations
result:    0,05066964

sparse1.Fredou
216ms   568747ticks 10000iterations
result:    0,8925781

sparse1.Marten
296ms   778862ticks 10000iterations
result:    0,05066964

sparse1.Fredou
216ms   568601ticks 10000iterations
result:    0,8925781

sparse1.Marten
300ms   789901ticks 10000iterations
result:    0,05066964

sparse1.Cyclone
1314ms   3457988ticks 10000iterations
result:    0,7851563

sparse1.Fredou
207ms   546606ticks 10000iterations
result:    0,8925781

sparse1.Marten
298ms   786352ticks 10000iterations
result:    0,05066964

sparse1.Cyclone
1301ms   3422611ticks 10000iterations
result:    0,7851563

sparse1.Marten
292ms   769850ticks 10000iterations
result:    0,05066964

sparse1.Cyclone
1305ms   3433320ticks 10000iterations
result:    0,7851563

sparse1.Fredou
209ms   551178ticks 10000iterations
result:    0,8925781

(测试脚本复制在这里，如果我破坏了你的修改它让我知道。https://dotnetfiddle.net/h9nFSa)

Answer 1

怎么样this one - dotnetfiddle example

using System;

namespace ConsoleApplication1
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int a = Convert.ToInt32("0001101", 2);
            int b = Convert.ToInt32("1100101", 2);

            Console.WriteLine(dendrite(a, 4, b));

        }

        private static float dendrite(int mask, int len, int input)
        {
            return  1 - getBitCount(mask ^ (input & (int.MaxValue >> 32 - len))) / (float)len;            
        }

        private static int getBitCount(int bits)
        {
            bits = bits - ((bits >> 1) & 0x55555555);
            bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
            return ((bits + (bits >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
        }
    }
}

64位一here - dotnetfiddler

using System;

namespace ConsoleApplication1
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //                                                                                      1
            ulong a = Convert.ToUInt64("0000000000000000000000000000000000000000000000000000000000001101", 2);
            ulong b = Convert.ToUInt64("1110010101100101011001010110110101100101011001010110010101100101", 2);

            Console.WriteLine(dendrite(a, 4, b));

        }

        private static float dendrite(ulong mask, int len, ulong input)
        {
            return 1 - getBitCount(mask ^ (input & (ulong.MaxValue >> (64 - len)))) / (float)len;            
        }

        private static ulong getBitCount(ulong bits)
        {
            bits = bits - ((bits >> 1) & 0x5555555555555555UL);
            bits = (bits & 0x3333333333333333UL) + ((bits >> 2) & 0x3333333333333333UL);
            return unchecked(((bits + (bits >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56;
        }
    }
}