Comparing bits efficiently ( overlap set of x )

Question

I want to compare a stream of bits of arbitrary length to a mask in c# and return a ratio of how many bits were the same. The mask to check against is anywhere between 2 bits long to 8k (with 90% of the masks being 5 bits long), the input can be anywhere between 2 bits up to ~ 500k, with an average input string of 12k (but yeah, most of the time it will be comparing 5 bits with the first 5 bits of that 12k)

Now my naive implementation would be something like this:

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;
}

but I expect this is better handled (more efficient) with some kind of binary operator magic?

Anyone got any pointers?

EDIT: the datatype is not fixed at this point in my design, so if ints or bytearrays work better, I'd also be a happy camper, trying to optimize for efficiency here, the faster the computation, the better.

eg if you can make it work like this:

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;
}

or this:

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 

ANSWER: I ran each proposed answer against each other and Fredou's and Marten's solution ran neck to neck but Fredou submitted the fastest leanest implementation in the end. Of course since the average result varies quite wildly between implementations I might have to revisit this post later on. :) but that's probably just me messing up in my test script. ( i hope, too late now, going to bed =)

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

( testscript copied here, if i destroyed yours modifying it lemme know. https://dotnetfiddle.net/h9nFSa )

Answer 1

I would change the code to something along these lines:

// hardcoded bitmask
byte mask = 255; 
float dendrite(byte input) { 
  int correct = 0;

  // store the xor:ed result
  byte xored = input ^ mask;

  // loop through each bit 
  for(int i = 0; i < 8; i++) {
    // if the bit is 0 then it was correct
    if(!(xored & (1 << i)))
      correct++;
   }
   return (float)correct/(float)mask.length;
}

The above uses a mask and input of 8 bits, but of course you could modify this to use a 4 byte integer and so on.

Not sure if this will work as expected, but it might give you some clues on how to proceed.

For example if you only would like to check the first 4 bits you could change the code to something like:

float dendrite(byte input) { 
  // hardcoded bitmask i.e 1101
  byte mask = 13;  
  // number of bits to check
  byte bits = 4;

  int correct = 0;

  // store the xor:ed result
  byte xored = input ^ mask;

  // loop through each bit, notice that we only checking the first 4 bits
  for(int i = 0; i < bits; i++) {
    // if the bit is 0 then it was correct
    if(!(xored & (1 << i)))
      correct++;
   }
   return (float)correct/(float)bits;
}

Of course it might be faster to actually use a int instead of a byte.

Answer 2

I came up with this code:

static float dendrite(ulong input, ulong mask)
{
    // get bits that are same (0 or 1) in input and mask
    ulong samebits = mask & ~(input ^ mask);

    // count number of same bits
    int correct = cardinality(samebits);

    // count number of bits in mask
    int inmask = cardinality(mask);

    // compute fraction (0.0 to 1.0)
    return inmask == 0 ? 0f : correct / (float)inmask;
}

// this is a little hack to count the number of bits set to one in a 64-bit word
static int cardinality(ulong word)
{
    const ulong mult = 0x0101010101010101;
    const ulong mask1h = (~0UL) / 3 << 1;
    const ulong mask2l = (~0UL) / 5;
    const ulong mask4l = (~0UL) / 17;

    word -= (mask1h & word) >> 1;
    word = (word & mask2l) + ((word >> 2) & mask2l);
    word += word >> 4;
    word &= mask4l;

    return (int)((word * mult) >> 56);
}

This will check 64-bits at a time. If you need more than that you can just split the input data into 64-bit words and compare them one by one and compute the average result.

Here's a .NET fiddle with the code and a working test case:
https://dotnetfiddle.net/5hYFtE

Answer 3

how about 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 bits one 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;
        }
    }
}