Date: 05/04/05 (C Sharp)    Keywords: no keywords

Remember some time ago I asked for the collection that has Add() and Contains() methods and a least possible overhead? Here we are. This is a specialized collection of this kind that will work for positive integers.

    public class BitSet
    {
        private const int BIT_COUNT = 64;
        private ulong[] data;

        private int count = 0;
        public int Count { get { return count; } }

        public int[] Values
        {
            get
            {
                int index = 0;
                int[] values = new int[count];
                for (int i = 0; i < data.Length * BIT_COUNT; i++)
                    if (Contains(i))
                        values[index++] = i;
                return values;
            }
        }

        public BitSet(int max_value)
        {
            data = new ulong[max_value / BIT_COUNT + 1];
        }

        public bool Contains(int value)
        {
            ulong bit_mask = (ulong)1 << (value % BIT_COUNT);
            return bit_mask == (data[value / BIT_COUNT] & bit_mask);
        }

        public void Add(int value)
        {
            if (!Contains(value))
            {
                data[value / BIT_COUNT] |= (ulong)1 << (value % BIT_COUNT);
                count++;
            }
        }

        public void Remove(int value)
        {
            if (Contains(value))
            {
                data[value / BIT_COUNT] ^= (ulong)1 << (value % BIT_COUNT);
                count--;
            }
        }

        public void Clear()
        {
            for (int i = 0; i < data.Length; i++)
                data[i] = 0;
        }
    }

Source: http://www.livejournal.com/community/csharp/28738.html