BitArray shift left/right confusion.

[Jakub Łabaj]

I was looking at the issues you reported and was pretty surprised 
how some of the features work. So I'm going to revive this thread 
with an explanation.

On Wednesday, 27 December 2017 at 20:45:49 UTC, Biotronic wrote:
> On Wednesday, 27 December 2017 at 18:08:19 UTC, Bastiaan Veelo 
> wrote:
>> I suppose the following is not a bug, but confusing it is:
>>
>> ```
>> void main()
>> {
>>     import std.stdio;
>>     import std.bitmanip;
>>     BitArray ba = [1, 1, 1, 1, 1, 1, 1, 1];
>>     writeln(ba);	// [1, 1, 1, 1, 1, 1, 1, 1]
>>     ba >>= 4;		// right shift
>>     writeln(ba);	// [1, 1, 1, 1, 0, 0, 0, 0] bits shifted left
>> }```
>>
>> I suppose this is because the array is printed left-to-right, 
>> whereas the bits in a byte are typically ordered right-to-left.

BitArray stores its data in a `size_t[]` array - on 64-bit it 
consists of 8-byte units, each unit having its beginning at the 
least significant bit. So it works as you would probably expect:

bool[128] bits;
auto ba = BitArray(bits); // one bool corresponds to one bit in 
this constructor
ba[0] = 1;
ba[127] = 1;

Now, the exact representation of the array in this BitArray is as 
follows:
index:  | 0          | 1          |
bit no: | 64 ... 1 0 | 63 ... 1 0 |
values: | 0  ... 0 1 | 1  ... 0 0 |

You can get this array using cast:
size_t[] exact = cast(size_t[]) ba;
assert(exact[0] == 1);
assert(exact[1] == size_t(1) << 63);

Printing works in the human, i.e. logical, way:
writeln(ba); // [1, 0, ..., 0, ..., 0, 1]

BitArray has also a constructor taking a raw representation of 
the underlying array:
size_t val = 0b1111_0000;
auto ba2 = BitArray([val], 8);
writeln(ba2); // [0, 0, 0, 0, 1, 1, 1, 1]

It may be surprising, as it's opposite order of the binary 
literal. But this works as intended because it's supposed to be 
the inversion of casting:
assert(cast(size_t[]) ba2 == [val]);
It also works like that e.g. in Java's BitSet and C++'s bitset.

On the other hand, shifting operators are equally confusing for 
me, as they are for you - they really work in the other way 
around! I thought this is a very weird bug, but I found this pull 
request: https://github.com/dlang/phobos/pull/2844, which states 
this is the intended behaviour.

I don't know if there is anybody that would expect this - it's 
inconsistent with any other bitset implementation I know from 
other languages, as well as with what logic suggests. I'm curious 
if the authors changed their minds in this regard and there is 
any chance for that to be rewritten?

And besides, it's pretty bugged, indeed.