BitArray/BitFields - Review

bearophile bearophileHUGS at lycos.com
Sun Jul 29 07:41:46 PDT 2012


Era Scarecrow:

As you guess I have had to use many arrays of bits in my programs 
:-)

> 4124 - Set/reset all bits ie:
>   BitArray ba = BitArray(100);
>   ba[] = true;
> Others haven't been done yet.

Among those 4124 suggestions the most important, and very simple 
to implement, are:
- set n-th bit (this can be a little more efficient than bs[n]=1;)
- reset n-th bit (this can be a little more efficient than 
bs[n]=1;)

Another commonly needed operation is a very fast bit count. There 
are very refined algorithms to do this.


> 7487 - Done. When prepending it extends the array to size_t 
> extra and slowly backtracks until it needs to do it again.

Leaving a bit of "capacity" at the beginning is a good idea.


> 7488 - Done, union used and is 'compact' version (by default or 
> resized and can fit)

Good, this makes BitArray usable in many other situations :-)


>> Related:
>> http://d.puremagic.com/issues/show_bug.cgi?id=6697
>
>  Not so sure. Could make a multi-dimentional one that returns 
> slices to various sections, but  that's iffy. I'd need an 
> example of how you'd use it with BitArray before I could build 
> a solution.

I have needed many times a fast BitMatrix, but I see it as a data 
structure distinct from BitArray, so don't worry about making 
them inter-operate.

For me a BitMatrix must be as fast as possible, even if this 
causes some waste of memory (see my implementation in the attach 
of issue 6697) and I use it for medium and large bit matrices. 
Generally I don't to count the set bits in a bit matrix. So the 
two data structures need different capabilities and they are 
better implemented in different ways (this means a FastBitMatrix 
is not an array of a BitArray!).

Taking a row of a FastBitMatrix and turning it into a a BitArray 
sounds cute, but generally I don't need to do this operation, so 
I don't care about this feature.

Bye,
bearophile


More information about the Digitalmars-d-learn mailing list