BitArray - Is there one?

[Dmitry Olshansky]

On 29.05.2012 4:13, Era Scarecrow wrote:
> On Monday, 28 May 2012 at 21:59:36 UTC, Dmitry Olshansky wrote:
>>
>> Check your math. Xor != sub.
>> 1 ^ 0 == 1, 0 ^ 1 == 1;
>> Compare with
>> 1 <sub> 0 == 1, 0 <sub> 1 == 0.
>>
>> That is, for one thing, sub is asymmetric :)
>
> Hmm well subs would all happen at the 1 bit level. So let's compare.
> xor
> 0 ^ 0 = 0
> 0 ^ 1 = 1
> 1 ^ 0 = 1
> 1 ^ 1 = 0
>
> sub
> 0 - 0 = 0
> 0 - 1 = -1 (or non-zero/true, truncates to 1)
> 1 - 0 = 1
> 1 - 1 = 0

You surely haven't looked at the source code did you? :)
BitArray opSub(BitArray e2)
{
	BitArray result;
	
         result.length = len;
         for (size_t i = 0; i < dim; i++)
             result.ptr[i] = this.ptr[i] & ~e2.ptr[i];
         return result;
}
It's conceptualy non per bit '-', it's a set difference...

>
>> Alas the other primary thing it lacks aside from set operators
>> overloading is Small string optimization. Namely you have some 8bytes
>> here, that's more then enough to store say 7*8=56 bits, and have 7
>> bits for length. Presumably you check if it's a small set by using
>> lower bit of a pointer. e.g. 0 == normal pointer, big set. if set to 1
>> == small set, everything else in next 3 bits of "pointer" are
>> small-length, all other 7 bytes of the whole struct contain bit-array.
>> You still can operate on it as 2 words.
>
> Union work. Could do it, but it then requires special rules. To do
> slices I have 2 longs representing the offset and ending bits within the
> size_t array, so we're looking at 192-256 bits. minus 16 will still
> leave us with 128 workable bits.
>
> Dealing with the pointer seems like a bad idea, but my starting offset
> we can say the first two bytes are 255, dropping the usable range of the
> starting offset to about 2^64 - 2^32, That could work and keep almost
> all the functionality.
>

Not at all. Once you established that it's not a pointer namely since 
every pointer to size_t is word aligned (unless constructed by hand).
You could use it's lowest bit as marker then. It's 0 state won't disturb 
pointer usual semantics, when it's set to 1 it's obviously

>> Then it can have very interesting use cases. Like say completely
>> replace usual nitty-gritty C-ish bit-flags. They sadly are too cost
>> effective so that no suitable safe alternative came about yet. Time to
>> make a game changer? ;)
>
> I don't see BitArray as a good replacement for the C flags. However I
> already made (and suggested) a flags struct that accepts and uses enums
> for it's flags.
>

Cool. Eager to see that on the way to Phobos too.

>> (and of course this optimization would be very welcome, I'll happily
>> bash any walls in front of such contribution making into Phobos)
>
> Then I'll import it and Hope I don't get too much criticism from the
> community.


-- 
Dmitry Olshansky