4

Since a boolean actually takes 1 byte of space, a bool[] isn't the most space-efficient way to represent a bit array. Sometimes integers and longs are used as a more efficient bit array, but a long can only hold 64 bits. Is there a more space-efficient way to store arrays of tens of millions bits in limited memory?

All I need to do with this array is to set/clear individual bits and to check whether some bits is 1 or 0, i.e. the only functions I need:

void Set(int index, bool value);
bool Get(int index);
Community
  • 1
  • 1
Louis Rhys
  • 34,517
  • 56
  • 153
  • 221

1 Answers1

11

I think what you need is BitArray class

I4V
  • 34,891
  • 6
  • 67
  • 79
  • Biggest issue with this class is that it doesn't implement the appropriate generic collection interfaces. Probably not a problem for the OP if he only needs those two operations though. – CodesInChaos Feb 10 '13 at 15:06
  • 3
    @CodesInChaos: And what kind of generic type will you expose? Your point is moot. – leppie Feb 10 '13 at 15:08
  • @leppie Implementing `IList` would have been appropriate IMO. I'm a bit surprised they didn't add that with .net 2.0, just like they added it to normal arrays. – CodesInChaos Feb 10 '13 at 15:11
  • 1
    @CodesInChaos from the docs it seems that this does not support operations that changes the length of the array. So probably implementing `IList` will make it more complicated. – Louis Rhys Feb 10 '13 at 15:14
  • @CodesInChaos And you can still use `bitArray.OfType().ToList()` – I4V Feb 10 '13 at 15:15
  • @LouisRhys Just throw `NotSupportedException` just like they already do for arrays or their `ICollection` implementation on `BitArray`. – CodesInChaos Feb 10 '13 at 15:16
  • @CodesInChaos I don't think it's a good idea. If people pass around BitArray as IList, they will get NotSupportedException without expecting it. – Louis Rhys Feb 10 '13 at 15:18
  • 1
    @LouisRhys The same issue applies to `bool[]`. You can't change the size of normal arrays either. IMO `BitArray` should mirror the semantics of `bool[]` as closely as possible, apart from the more efficient storage. | The design of .net's interfaces is dumb, but that's a different issue. – CodesInChaos Feb 10 '13 at 15:20