Most efficient way to reverse the order of a BitArray?

Question

I've been wondering what the most efficient way to reverse the order of a BitArray in C#. To be clear, I don't want to inverse the Bitarray by calling .Not(), I want to reverse the order of the bits in the array.

Cheers, Chris

Boodle

How about just using (reading) it backward? – Debarath

Yes, the size is fixed (8 bits) – Boodle

Answer 1

public void Reverse(BitArray array)
{
    int length = array.Length;
    int mid = (length / 2);

    for (int i = 0; i < mid; i++)
    {
        bool bit = array[i];
        array[i] = array[length - i - 1];
        array[length - i - 1] = bit;
    }    
}

Sidneysidoma

Please add this to official dotnet code someone – Worldlywise

Answer 2

For a long array and relative few uses, just wrap it:

    class BitArrayReverse
    {
        private BitArray _ba;

        public BitArrayReverse(BitArray ba) { _ba = ba; }

        public bool this[int index]
        {
            get { return _ba[_ba.Length - 1 - index]; }
            set { _ba[_ba.Length - 1 - index] = value; }
        }

    }

Debarath

+1 Nice. Not really an answer but clever option for some situations. – Patnode

Answer 3

This will be the best way to reverse MSB <-> LSB of any length using XOR in the for loop

public static BitArray BitsReverse(BitArray bits)
{
    int len = bits.Count;
    BitArray a = new BitArray(bits);
    BitArray b = new BitArray(bits);

    for (int i = 0, j = len-1; i < len; ++i, --j)
    {
         a[i] = a[i] ^ b[j];
         b[j] = a[i] ^ b[j];
         a[i] = a[i] ^ b[j];
    }

    return a; 
} 
// in   010000011010000011100b
// out  001110000010110000010b

Sepia

You triple memory consumption and assigning operations. How this can be efficient? – Worldlywise

Answer 4

 Dim myBA As New BitArray(4)
 myBA(0) = True
 myBA(1) = False
 myBA(2) = True
 myBA(3) = True
 Dim myBoolArray1(3) As Boolean
 myBA.CopyTo(myBoolArray1, 0)
 Array.Reverse(myBoolArray1)
 myBA = New BitArray(myBoolArray1)

Hereof

Answer 5

For a short but inefficient answer:

using System.Linq;

var reversedBa = new BitArray(myBa.Cast<bool>().Reverse().ToArray())

William

Answer 6

Because the size if fixed at 8-bits just the "table" lookup from below is sufficient -- when dealing with a plain byte a look-up is likely the quickest way. The extra overhead of BitSet to get/set the data may, however, nullify the look-up benefit. Also the initial build cost and persistent overhead need to be considered (but the values could be coded into an array literal ... ick!)

On the other hand, if the data is only 8 bit (ever), and "performance is important", why use a BitArray at all? A BitArray could always be used for the nice features, such as "exploding" to an Enumerable while C# already has decent byte bit manipulation built-in.

Assuming a more general case that the data is 8-bit aligned... but of some undetermined length

Is this actually better (faster, more efficient, etc) than just doing it "per item" in the BitArray? I have no idea but suspect not. I would definitely start with the "simple" methods -- this is here as just a proof-of-concept and may (or may not be) interesting to compare in a benchmark. Anyway, write for clarity first ... and the below is not it! (There is at least one bug in it -- I blame the extra complexity ;-)

byte reverse (byte b) { 
    byte o = 0;
    for (var i = 0; i < 8; i++) {
        o <<= 1;
        o |= (byte)(b & 1);
        b >>= 1;
    }
    return o;
}

byte[] table;
BitArray reverse8 (BitArray ar) {
    if (ar.Count % 8 != 0) {
        throw new Exception("no!");
    }

    byte[] d = new byte[ar.Count / 8];
    ar.CopyTo(d, 0);

    // this only works if the bit array is
    // a multiple of 8. we swap bytes and
    // then reverse bits in each byte
    int mid = d.Length / 2; 
    for (int i = 0, j = d.Length - 1; i < mid; i++, j--) {
        byte t = d[i];
        d[i] = table[d[j]];
        d[j] = table[t];
    }

    return new BitArray(d);
}

string tostr (BitArray x) {
    return string.Join("",
        x.OfType<bool>().Select(i => i ? "1" : "0").ToArray());
}

void Main()
{
    table = Enumerable.Range(0,256).Select(v => reverse((byte)v)).ToArray();
    {
        byte[] s = new byte[] { 1, 0xff };  
        BitArray ar = new BitArray(s);  
        // linqpad :)
        tostr(ar).Dump();
        tostr(reverse8(ar)).Dump();
    }
    "--".Dump();
    {
        byte[] s = new byte[] { 3, 42, 19 };
        BitArray ar = new BitArray(s);  
        // linqpad :)
        tostr(ar).Dump();
        tostr(reverse8(ar)).Dump();
    }   
}

Output:

1000000011111111
1111111100000001
--
110000000101010011001000
000100110101010000000011

The expr.Dump() is a LINQPad feature.

Flagstad

Answer 7

Adapted the answer from @TimLoyd and turned it into an extension for easier use.

public static BitArray Reverse(this BitArray array)
{
    int length = array.Length;
    int mid = (length / 2);

    for (int i = 0; i < mid; i++)
    {
        bool bit = array[i];
        array[i] = array[length - i - 1];
        array[length - i - 1] = bit;
    }

    return new BitArray(array);
}

Usage:

var bits = new BitArray(some_bytes).Reverse();

Stadia