BitArray - Is there one?

[Dmitry Olshansky]

On 29.05.2012 11:25, Era Scarecrow wrote:
> On Tuesday, 29 May 2012 at 06:56:40 UTC, Dmitry Olshansky wrote:
>> On 29.05.2012 10:52, Era Scarecrow wrote:
>>> I considered that, but then you actually limit your address space to
>>> 2^63,
>>
>> No you don't. Since pointer is already a pointer to word-sized object.
>> It has 2 last bits == 0. Always. There is no escaping of this fact.
>> And no your address space is intact. All it has to do is assuming
>> proper alignment, and you sure have it since you _allocate_ it.
>
>> To be more specific most allocator go even farther and provide 8bytes
>> aligned pointer.
>
> Don't you mean the first 2 bits? (being least significant). Even so,
> that seems more like its working out of coincidence, that or you can
> never use more than 25% of your memory in a single address space in your
> program (ever).

Yes, least significant. no you memory is intact.
I think it's a classical case of you not getting how it works.
No problem, bear with me :)

Suppose you have array of size_t, let size_t.sizeof == 4.
Here it is:
data: 	a0 a1 a2 a3 a4 ...
addr:	20 24 28 32 36 ...

Noticed the pattern? Once first address is multiple of 4 (that is 
properly aligned) it can't become not a multiple of 4.
Meaning that 2 least significant bits are always == 0.

The memory is not wasted since address is incremented by 4 bytes at a 
time, and is read by a unit of 4 bytes.

-- 
Dmitry Olshansky