using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Globalization;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

​

namespace sparse1

{

    public class Program

    {

        private static ulong[] masks = new ulong[]

        {

            20, 300, 12, 65535, 3223, 1234, 12, 655352

        };

​

        //split input in chunks of ulong.maxsize 

        private static ulong[] data = new ulong[]

        {

            12000, 232, 2323, 31212, 131232232323, 12332, 2313213132, 3232, 32312, 5454, 2, 958454, 54, 4545,

            454545, 45543543534, 53454353, 5544443, 244535353, 35353433434, 35353, 53534212344, 34344343, 43434434,

            334444433443, 3434334434343, 34224323, 2432, 23333, 3332, 2232322332323, 334343, 22323, 32223, 1, 3232, 32,

            12, 3, 231345353, 1332, 2

        };

​

        public static void Main(string[] args)

        {

            IDendrite[] dendrites = new IDendrite[] { new Cyclone(), new Marten(), new Fredou(), new Marten(), new Cyclone(), new Fredou(), new Fredou(), new Cyclone(), new Marten()  };

            Stopwatch sw = new Stopwatch();

            StringBuilder sb = new StringBuilder(); 

            float[] results = new float[0];

            int x = 0;

            int iter = 10000;

            sw.Start();

            sw.Reset();

            foreach (IDendrite dendrite in dendrites)

            {

                x = 0;

                results = new float[0];

                sw.Start();

                while (x++ < iter)

                {

                    results = new float[masks.Length];

                    foreach (var input in data)

                    {

                        for (int i = 0, l = masks.Length; i < l; i++)

                        {

                            results[i] = dendrite.dendrite(masks[i], 64, input);

                        }

                    }

                }

                sw.Stop();

                sb.AppendFormat("{0}\n" +

                                "{1}ms   {2}ticks {3}iterations\nresult:    {4}\n", 

                                dendrite.ToString(), 

                                sw.ElapsedMilliseconds.ToString(),

                    sw.ElapsedTicks.ToString(), iter.ToString(), 

                    results.Average().ToString());

                var wtf = sw.ElapsedTicks;

                sw.Reset();

            }

            Console.WriteLine(sb.ToString());

            Console.ReadKey();

        }

​

    }

​

    interface IDendrite

    {

        float dendrite(ulong mask, int len, ulong input);

    }

    class Fredou : IDendrite

    {

        public float dendrite(ulong mask, int len, ulong input)

        {

            return 1 - getBitCount(mask ^ (input & (ulong.MaxValue >> (64 - len)))) / (float)len;

        }

​

        private ulong getBitCount(ulong bits)

        {

            bits = bits - ((bits >> 1) & 0x5555555555555555UL);

            bits = (bits & 0x3333333333333333UL) + ((bits >> 2) & 0x3333333333333333UL);

            return unchecked(((bits + (bits >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56;

        }

​

    }

​

    class Marten : IDendrite

    {

        public float dendrite(ulong mask, int len, ulong input)

        {

            // 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);

        }

    }

​

    class Cyclone : IDendrite

    {

        public float dendrite(ulong mask, int len, ulong input)

        {

            int correct = 0;

​

            // store the xor:ed result

            ulong xored = input ^ mask;

​

            // loop through each bit 

            for (int i = 0; i < len; i++)

            {

                // if the bit is 0 then it was correct

                if (0==(xored & (ulong)(1 << i)))

                    correct++;

            }

            return (float) correct/64;//(float)mask.Length;

        }

    }

​

}

​