What is the C# equivalent of BitSet of Java?

Question

My requirements are simple:

1. Be able to define dimensions of bit array, i.e: 5 bytes.
2. bool Get(bitIndex: int)
3. Set(bitIndex: int)

Is there a c# equivalent which provides similar functionality to BitSet in Java?

Here's the scenario:

1. Initialize 5 bytes, all bits are 0(false).
2. Set byte 3, bit 8 to TRUE.
3. Get status of byte 3, bit 8.

UPDATE: Solution from Michael Bray:

static void Main(string[] args) 
{ 
  // Set for 5 bytes 
  BitArray ba = new BitArray(8 * 5); 

  // Set bit #1 on byte #4 
  ba.Set(GetBitNum(4, 1), true); 

  // Get bit #1 on byte #4 
  bool v = ba.Get(GetBitNum(4, 1)); 
} 

static int GetBitNum(int byteNum, int bitNum)   // Assumes index starts at 1 
{ 
  return (byteNum - 1) * 8 + (bitNum - 1); 
}

Answer 1

System.Collections.BitArray is pretty close, but it's a bit lacking in features. I wrote a helper class that implements a lot of features you might need for BitArray some time ago, but I'd have to dig it up. Let me know if you think you need it.

EDIT: As requested in the comments below, I've posted the code at http://pastebin.com/GLyzcUZC. As I discuss, though, it's benefits over stock BitArray are minimal, as I wrote it for some specific needs that I had. Do with it as you wish.

EDIT 2: As Miguel pointed out in the comments, there are some implementation issues that make my 'BitArray' code not so good... I had already realized the deficiencies and had re-written a new version called BoolArray (to distinguish from BitArray) that doesn't suffer from those problems :

namespace Utils
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Globalization;
    using System.Linq;
    using System.Threading;

    /// <summary>
    /// A replacement for BitArray
    /// </summary>
    public class BoolArray : IEnumerable, ICollection, ICloneable
    {
        private UInt32[] bits = null;
        private int _length = 0;
        private static UInt32 ONE = (UInt32)1 << 31;
        private object _syncRoot;
        private static Func<byte[], byte[]> EndianFixer = null;

        #region Constructors

        static BoolArray()
        {
            if (BitConverter.IsLittleEndian) EndianFixer = (a) => a.Reverse().ToArray();
            else EndianFixer = (a) => a;
        }

        public BoolArray(BoolArray srcBits)
        {
            this.InitializeFrom(srcBits.ToArray());
        }

        public BoolArray(BitArray srcBits)
        {
            this._length = srcBits.Count;
            this.bits = new UInt32[RequiredSize(this._length)];

            for (int i = 0; i < srcBits.Count; i++) this[i] = srcBits[i];
        }

        public BoolArray(int v)
        {
            ICollection<byte> bytes = EndianFixer(BitConverter.GetBytes(v)).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(ICollection<bool> srcBits)
        {
            this.InitializeFrom(srcBits.ToArray());
        }

        public BoolArray(ICollection<byte> srcBits)
        {
            InitializeFrom(srcBits);
        }

        public BoolArray(ICollection<short> srcBits)
        {
            ICollection<byte> bytes = srcBits.SelectMany(v => EndianFixer(BitConverter.GetBytes(v))).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(ICollection<ushort> srcBits)
        {
            ICollection<byte> bytes = srcBits.SelectMany(v => EndianFixer(BitConverter.GetBytes(v))).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(ICollection<int> srcBits)
        {
            ICollection<byte> bytes = srcBits.SelectMany(v => EndianFixer(BitConverter.GetBytes(v))).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(ICollection<uint> srcBits)
        {
            ICollection<byte> bytes = srcBits.SelectMany(v => EndianFixer(BitConverter.GetBytes(v))).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(ICollection<long> srcBits)
        {
            ICollection<byte> bytes = srcBits.SelectMany(v => EndianFixer(BitConverter.GetBytes(v))).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(ICollection<ulong> srcBits)
        {
            ICollection<byte> bytes = srcBits.SelectMany(v => EndianFixer(BitConverter.GetBytes(v))).ToList();
            InitializeFrom(bytes);
        }

        public BoolArray(int capacity, bool defaultValue = false)
        {
            this.bits = new UInt32[RequiredSize(capacity)];
            this._length = capacity;

            // Only need to do this if true, because default for all bits is false
            if (defaultValue) for (int i = 0; i < this._length; i++) this[i] = true;
        }

        private void InitializeFrom(ICollection<byte> srcBits)
        {
            this._length = srcBits.Count * 8;
            this.bits = new UInt32[RequiredSize(this._length)];
            for (int i = 0; i < srcBits.Count; i++)
            {
                uint bv = srcBits.Skip(i).Take(1).Single();
                for (int b = 0; b < 8; b++)
                {
                    bool bitVal = ((bv << b) & 0x0080) != 0;
                    int bi = 8 * i + b;
                    this[bi] = bitVal;
                }
            }
        }

        private void InitializeFrom(ICollection<bool> srcBits)
        {
            this._length = srcBits.Count;
            this.bits = new UInt32[RequiredSize(this._length)];

            int index = 0;
            foreach (var b in srcBits) this[index++] = b;
        }

        private static int RequiredSize(int bitCapacity)
        {
            return (bitCapacity + 31) >> 5;
        }

        #endregion

        public bool this[int index]
        {
            get
            {
                if (index >= _length) throw new IndexOutOfRangeException();

                int byteIndex = index >> 5;
                int bitIndex = index & 0x1f;
                return ((bits[byteIndex] << bitIndex) & ONE) != 0;
            }
            set
            {
                if (index >= _length) throw new IndexOutOfRangeException();

                int byteIndex = index >> 5;
                int bitIndex = index & 0x1f;
                if (value) bits[byteIndex] |= (ONE >> bitIndex);
                else bits[byteIndex] &= ~(ONE >> bitIndex);
            }
        }

        #region Interfaces implementation
        #region IEnumerable
        public IEnumerator GetEnumerator()
        {
            //for (int i = 0; i < _length; i++) yield return this[i];
            return this.ToArray().GetEnumerator();
        }
        #endregion
        #region ICollection
        public void CopyTo(Array array, int index)
        {
            if (array == null) throw new ArgumentNullException("array");
            if (index < 0) throw new ArgumentOutOfRangeException("index");
            if (array.Rank != 1) throw new ArgumentException("Multidimensional array not supported");
            if (array is UInt32[]) Array.Copy(this.bits, 0, array, index, (this.Count + sizeof(UInt32) - 1) / sizeof(UInt32));
            else if (array is bool[]) Array.Copy(this.ToArray(), 0, array, index, this.Count);
            else throw new ArgumentException("Array type not supported (UInt32[] or bool[] only)");

        }

        public int Count
        {
            get { return this._length; }
            private set
            {
                if (value > this._length) Extend(value - this._length);
                else this._length = Math.Max(0, value);
            }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get
            {
                if (this._syncRoot == null) Interlocked.CompareExchange<object>(ref this._syncRoot, new object(), null);
                return _syncRoot;
            }
        }
        #endregion
        #region ICloneable
        public object Clone()
        {
            return new BoolArray(this);
        }
        // Not part of ICloneable, but better - returns a strongly-typed result
        public BoolArray Dup()
        {
            return new BoolArray(this);
        }
        #endregion 
        #endregion

        #region String Conversions

        public override string ToString()
        {
            return ToBinaryString();
            //return ToHexString(" ", " ■ ");
        }

        public static BoolArray FromHexString(string hex)
        {
            if (hex == null) throw new ArgumentNullException("hex");

            List<bool> bits = new List<bool>();
            for (int i = 0; i < hex.Length; i++)
            {
                int b = byte.Parse(hex[i].ToString(), NumberStyles.HexNumber);
                bits.Add((b >> 3) == 1);
                bits.Add(((b & 0x7) >> 2) == 1);
                bits.Add(((b & 0x3) >> 1) == 1);
                bits.Add((b & 0x1) == 1);
            }
            BoolArray ba = new BoolArray(bits.ToArray());
            return ba;
        }

        public string ToHexString(string bitSep8 = null, string bitSep128 = null)
        {
            string s = string.Empty;
            int b = 0;
            bool[] bbits = this.ToArray();

            for (int i = 1; i <= bbits.Length; i++)
            {
                b = (b << 1) | (bbits[i - 1] ? 1 : 0);
                if (i % 4 == 0)
                {
                    s = s + string.Format("{0:x}", b);
                    b = 0;
                }

                if (i % (8 * 16) == 0)
                {
                    s = s + bitSep128;
                }
                else if (i % 8 == 0)
                {
                    s = s + bitSep8;
                }
            }
            int ebits = bbits.Length % 4;
            if (ebits != 0)
            {
                b = b << (4 - ebits);
                s = s + string.Format("{0:x}", b);
            }
            return s;
        }

        public static BoolArray FromBinaryString(string bin, char[] trueChars = null)
        {
            if (trueChars == null) trueChars = new char[] { '1', 'Y', 'y', 'T', 't' };
            if (bin == null) throw new ArgumentNullException("bin");
            BoolArray ba = new BoolArray(bin.Length);
            for (int i = 0; i < bin.Length; i++) ba[i] = bin[i].In(trueChars);
            return ba;
        }

        public string ToBinaryString(char setChar = '1', char unsetChar = '0')
        {
            return new string(this.ToArray().Select(v => v ? setChar : unsetChar).ToArray());
        }

        #endregion

        #region Class Methods
        public bool[] ToArray()
        {
            bool[] vbits = new bool[this._length];
            for (int i = 0; i < _length; i++) vbits[i] = this[i];
            return vbits;
        }

        public BoolArray Append(ICollection<bool> addBits)
        {
            int startPos = this._length;
            Extend(addBits.Count);
            bool[] bitArray = addBits.ToArray();
            for (int i = 0; i < bitArray.Length; i++) this[i + startPos] = bitArray[i];
            return this;
        }

        public BoolArray Append(BoolArray addBits)
        {
            return this.Append(addBits.ToArray());
        }

        public static BoolArray Concatenate(params BoolArray[] bArrays)
        {
            return new BoolArray(bArrays.SelectMany(ba => ba.ToArray()).ToArray());
        }

        private void Extend(int numBits)
        {
            numBits += this._length;
            int reqBytes = RequiredSize(numBits);
            if (reqBytes > this.bits.Length)
            {
                UInt32[] newBits = new UInt32[reqBytes];
                this.bits.CopyTo(newBits, 0);
                this.bits = newBits;
            }
            this._length = numBits;
        }

        public bool Get(int index)
        {
            return this[index];
        }

        public BoolArray GetBits(int startBit = 0, int numBits = -1)
        {
            if (numBits == -1) numBits = bits.Length;
            return new BoolArray(this.ToArray().Skip(startBit).Take(numBits).ToArray());
        }

        public BoolArray Repeat(int numReps)
        {
            bool[] oBits = this.ToArray();
            List<bool> nBits = new List<bool>();
            for(int i=0; i<numReps; i++) nBits.AddRange(oBits);
            this.InitializeFrom(nBits);
            return this;
        }

        public BoolArray Reverse()
        {
            int n = this.Count;
            for(int i=0; i<n/2; i++) 
            {
                bool b1 = this[i];
                this[i] = this[n - i - 1];
                this[n - i - 1] = b1;
            }
            return this;
        }

        public BoolArray Set(int index, bool v)
        {
            this[index] = v;
            return this;
        }

        public BoolArray SetAll(bool v)
        {
            for (int i = 0; i < this.Count; i++) this[i] = v;
            return this;
        }

        public BoolArray SetBits(ICollection<bool> setBits, int destStartBit = 0, int srcStartBit = 0, int numBits = -1, bool allowExtend = false)
        {
            if (setBits == null) throw new ArgumentNullException("setBits");
            if ((destStartBit < 0) || (destStartBit >= this.Count)) throw new ArgumentOutOfRangeException("destStartBit");
            if ((srcStartBit < 0) || (srcStartBit >= setBits.Count)) throw new ArgumentOutOfRangeException("srcStartBit");

            bool[] sBits;
            if (setBits is bool[]) sBits = (bool[])setBits;
            else sBits = setBits.ToArray();

            if (numBits == -1) numBits = setBits.Count;
            if (numBits > (setBits.Count - srcStartBit)) numBits = setBits.Count - srcStartBit;

            int diffSize = numBits - (this.Count - destStartBit);
            if (diffSize > 0)
            {
                if (allowExtend) Extend(diffSize);
                else numBits = this.Count - destStartBit;
            }
            for (int i = 0; i < numBits; i++) this[destStartBit + i] = sBits[srcStartBit + i];
            return this;
        }

        public List<BoolArray> SplitEvery(int numBits)
        {
            int i = 0;
            List<BoolArray> bitSplits = new List<BoolArray>();
            while (i < this.Count)
            {
                bitSplits.Add(this.GetBits(i, numBits));
                i += numBits;
            }
            return bitSplits;
        }

        public byte[] ToBytes(int startBit = 0, int numBits = -1)
        {
            if (numBits == -1) numBits = this._length - startBit;
            BoolArray ba = GetBits(startBit, numBits);
            int nb = (numBits + 7) / 8;
            byte[] bb = new byte[nb];
            for (int i = 0; i < ba.Count; i++)
            {
                if (!ba[i]) continue;
                int bp = 7 - (i % 8);
                bb[i / 8] = (byte)((int)bb[i / 8] | (1 << bp));
            }
            return bb;
        }


        #endregion

        #region Logical Bitwise Operations
        public BoolArray BinaryBitwiseOp(Func<bool, bool, bool> op, BoolArray ba, int start = 0)
        {
            for (int i = 0; i < ba.Count; i++)
            {
                if (start + i >= this.Count) break;
                this[start + i] = op(this[start + i], ba[i]);
            }
            return this;
        }

        public BoolArray Xor(BoolArray xor, int start = 0)
        {
            return BinaryBitwiseOp((a, b) => (a ^ b), xor, start);
        }

        public BoolArray And(BoolArray and, int start = 0)
        {
            return BinaryBitwiseOp((a, b) => (a & b), and, start);
        }

        public BoolArray Or(BoolArray or, int start = 0)
        {
            return BinaryBitwiseOp((a, b) => (a | b), or, start);
        }

        public BoolArray Not(int start = 0, int len = -1)
        {
            for (int i = start; i < this.Count; i++)
            {
                if (--len == -1) break;
                this[i] = !this[i];
            }
            return this;
        } 
        #endregion

        #region Class Operators

        public static BoolArray operator +(BoolArray a, BoolArray b)
        {
            return a.Dup().Append(b);
        }

        public static BoolArray operator |(BoolArray a, BoolArray b)
        {
            return a.Dup().Or(b);
        }

        public static BoolArray operator &(BoolArray a, BoolArray b)
        {
            return a.Dup().And(b);
        }

        public static BoolArray operator ^(BoolArray a, BoolArray b)
        {
            return a.Dup().Xor(b);
        }

        public static BoolArray operator ~(BoolArray a)
        {
            return a.Dup().Not();
        }

        public static BoolArray operator <<(BoolArray a, int shift)
        {
            return a.Dup().Append(new bool[shift]);
        }

        public static BoolArray operator >>(BoolArray a, int shift)
        {
            return new BoolArray(a.ToArray().Take(Math.Max(0, a.Count - shift)).ToArray());
        }

        public static bool operator ==(BoolArray a, BoolArray b)
        {
            if (a.Count != b.Count) return false;
            for (int i = 0; i < a.Count; i++) if (a[i] != b[i]) return false;
            return true;
        }
        public override bool Equals(object obj)
        {
            if (!(obj is BoolArray)) return false;
            return (this == (BoolArray)obj);
        }
        public override int GetHashCode()
        {
            return this.ToHexString().GetHashCode();
        }

        public static bool operator !=(BoolArray a, BoolArray b)
        {
            return !(a == b);
        }

        #endregion
    }
}

Answer 2

I had the same issue, but had more than just the one Cardinality method to convert. So, I opted to port the entire BitSet class. Fortunately it was self-contained.

Here is the Gist of the C# port.

I have also added it to the open source BoboBrowse.Net project.

I would appreciate if people would report any bugs that are found - I am not a Java developer, and have limited experience with bit logic, so I might have translated some of it incorrectly.