using System;

using System.Collections;

using System.Collections.Generic;

using System.Diagnostics;

​

public class Program

{

    public static Int32 CountArray(BitArray bitArray)

    {

        int count = 0;

        int[] tmp = new int[bitArray.Length];

        bitArray.CopyTo(tmp,0);

        foreach(int i in tmp)

        {

            if(i == 1)

                count++;

        }

        return count;

    }

    public static Int32 GetArrayCount(int[] ints)

    {

        Int32 count = 0;

        for (Int32 i = 0; i < ints.Length; i++)

        {

            Int32 c = ints[i];

            // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)

            unchecked

            {

                c = c - ((c >> 1) & 0x55555555);

                c = (c & 0x33333333) + ((c >> 2) & 0x33333333);

                c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

            }

​

            count += c;

        }

​

        return count;

    }

    public static Int32 GetCardinality(BitArray bitArray)

    {

        Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

        bitArray.CopyTo(ints, 0);

        Int32 count = 0;

        // fix for not truncated bits in last integer that may have been set to true with SetAll()

        ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));

        for (Int32 i = 0; i < ints.Length; i++)

        {

            Int32 c = ints[i];

            // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)

            unchecked

            {

                c = c - ((c >> 1) & 0x55555555);

                c = (c & 0x33333333) + ((c >> 2) & 0x33333333);

                c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

            }

​

            count += c;

        }

​

        return count;

    }

​

    public static void PrintArray(int[] array)

    {

        for (int i = 0; i < array.Length; i++)

        {

            Console.Write(array[i].ToString());

        }

​

        Console.Write('\n');

    }

​

    public static void Main()

    {

        System.Random rnd = new Random();

        int length = 200000;

        int list_length = 30;

        List<int[]> integer_list = new List<int[]>();

        List<BitArray> ba_list = new List<BitArray>();

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

        {

            int[] new_list = new int[length];

            for (int ca = 0; ca < new_list.Length; ca++)

            {

                int prob = rnd.Next(10);

                if(prob == 2)

                {

                    new_list[ca] = 1;

                }

                //new_list[ca] = rnd.Next(2);

            }

​

            BitArray ba_new = new BitArray(new_list);

            ba_list.Add(ba_new);

            integer_list.Add(new_list);

        }

        int[] d = new int[length];

        HashSet<int> int_hsh = new HashSet<int>(length);

        BitArray bd = null;

        int bitarray_count = 0;

        int loop_count = 0;

        Stopwatch bsw = new Stopwatch();

        Stopwatch sw = new Stopwatch();

        sw.Start();

        foreach (int[] list in integer_list)

        {

            for (int i = 0; i < list.Length; i++)

            {

                //d[i] = d[i] | list[i];

                d[i] = d[i] | list[i];

            }

        }

        loop_count = GetArrayCount(d);

        //foreach(int v in d)

        //{

        //  if(v == 1)

        //  {

        //      loop_count++;

        //  }

        //}

​

        sw.Stop();

        bsw.Start();

        foreach (BitArray current in ba_list)

        {

            if (bd == null)

            {

                bd = new BitArray(current);

            }

            else

            {

                bd.Or(current);

            }

        }

​

        bitarray_count = GetCardinality(bd);

        //bitarray_count = CountArray(bd);

        bsw.Stop();

        Console.WriteLine("Time Elapsed (Ticks): " + sw.ElapsedTicks.ToString());

        Console.WriteLine("Time Elapsed (Ms): " + sw.ElapsedMilliseconds.ToString());

        Console.WriteLine("Count: " + loop_count.ToString());

        Console.WriteLine("========================================================");

        Console.WriteLine("Time Elapsed (Ticks): " + bsw.ElapsedTicks.ToString());

        Console.WriteLine("Time Elapsed (Ms): " + bsw.ElapsedMilliseconds.ToString());

        Console.WriteLine("Count: " + bitarray_count.ToString());

        if (length < 1000)

        {

            foreach(int[] q in integer_list)

            {

                PrintArray(q);

            }

            Console.WriteLine("");

            int[] ba_int = new int[length];

            bd.CopyTo(ba_int, 0);

            PrintArray(d);

            PrintArray(ba_int);

        }

    }

}