BitArray - Shift bits

Question

I have a System.Collections.BitArray array (~3000 items) and I would like to shift all the bits to the left by 1. However the collection doesn't seem to support that operation (i.e. bitArray << 1 not working and there is no method). Any idea on how to do that?

Thanks!

Irrefrangible

Answer 1

This simple snippet shows a manual way to do it. The value of bitArray[0] is overwritten:

//... bitArray is the BitArray instance

for (int i = 1; i < bitArray.Count; i++)
{
   bitArray[i - 1] = bitArray[i];
}

bitArray[bitArray.Count - 1] = false // or true, whatever you want to shift in

Making this an extension method shouldn't be a big deal.

Malatya

That great... but slow. I though there would be a special operator or method since we are playing with bits. – Irrefrangible

You can go the long way of copying the content from your BitArray to a bool[] and than copy the data to another bool[] using offsets. Finally you could recreate your BitArray from the resulting bool[]. But I doubt it will be faster than accessing each element for your ~3000 bits. – Malatya

Answer 2

System.Numerics.BigInteger does indeed support bit shifting.

Slaphappy

With one caveat: "Unlike the bitwise left-shift operation with integer primitives, the LeftShift method preserves the sign of the original BigInteger value." So (-3 << 30) != ((BigInteger)(-3) << 30) – Cultrate

And the reason for this is BigInteger type is Signed. – Rhetor

Answer 3

I am not sure how about efficiency but this extension method does the job

public static BitArray ShiftRight(this BitArray instance)
{
    return new BitArray(new bool[] { false }.Concat(instance.Cast<bool>().Take(instance.Length - 1)).ToArray());
}

Asthma

OP asked for a shift left. I liked this, so here is a shift left version: return new BitArray( (instance.Cast<bool>().Take(instance.Length - 1).ToArray()).Concat(new bool[] { newState }).ToArray() ); – Shimmy

Indeed. Thanks :) – Asthma

Answer 4

Since Core 2.0 (7 years later after this question was asked) there is a built-in method .LeftShift() for this

BitArray.LeftShift(Int32) Method

Ulrick

Answer 5

Recreate bitarray yourself as a wrapper around ulong[]; implementing bitshifts by a number smaller than 64 is a piece of cake that way and it will take less time and kill fewer polar bears than the other suggested approaches. By wary of the "bits that would fall of the end", if you want to keep them you may have to grow the array (or not, if they are zero and you say that non-existing element implicitly hold zero).

Liven

Answer 6

The easiest way I'd go for off the top of my head is to convert the BitArray to a BigInt or similar structure that supports bitwise shifting and back. Now, the built-int BigInteger in .Net 4 doesn't support shifting I think, but there are others that do, like Mono's implementation.

Jamey