Cách hiệu quả nhất để đảo ngược thứ tự của một BitArray?

Question

Tôi đã tự hỏi cách hiệu quả nhất để đảo ngược thứ tự của một BitArray trong C#. Để được rõ ràng, tôi không muốn đảo ngược Bitarray bằng cách gọi. Không(), tôi muốn đảo ngược thứ tự của các bit trong mảng.

Chúc mừng, Chris

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; 
    }  
} 

Answer 2

Đối với một mảng dài và vài công dụng tương đối, chỉ cần quấn nó:

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; } 
     } 

    } 

Answer 3

Bởi vì kích thước nếu cố định ở mức 8-bit chỉ là "bảng" tra cứu từ bên dưới là đủ - khi giao dịch với số tiền là byte đồng nghĩa với việc tra cứu có thể là cách nhanh nhất. Tuy nhiên, chi phí bổ sung của BitSet để lấy/thiết lập dữ liệu có thể vô hiệu hóa lợi ích tra cứu. Ngoài ra chi phí xây dựng ban đầu và chi phí liên tục cần phải được xem xét (nhưng các giá trị có thể được mã hóa thành một mảng chữ ... ick!)

Mặt khác, nếu dữ liệu là chỉ 8 bit (bao giờ) và "hiệu suất là quan trọng", tại sao lại sử dụng BitArray? Một BitArray luôn luôn có thể được sử dụng cho các tính năng tốt đẹp, chẳng hạn như "bùng nổ" để một Enumerable trong khi C# đã có thao tác bit bit phong nha được xây dựng trong.

Giả sử một trường hợp tổng quát hơn rằng các dữ liệu được liên kết 8-bit ... nhưng một số chiều dài không xác định

Đây có phải là thực sự tốt hơn (nhanh hơn, hiệu quả hơn, vv) hơn là chỉ làm việc đó "cho mỗi mục "trong BitArray? Tôi không có ý tưởng nhưng nghi ngờ là không. Tôi chắc chắn sẽ bắt đầu với các phương pháp "đơn giản" - đây là đây chỉ là một chứng minh-khái niệm và có thể (hoặc có thể không) thú vị để so sánh trong một điểm chuẩn. Dù sao, viết cho rõ ràng đầu tiên ... và bên dưới không phải là nó! (Có ít nhất một lỗi trong nó - Tôi đổ lỗi cho thêm sự phức tạp ;-)

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 

Các expr.Dump() là một tính năng LINQPad.

Answer 4

Đây sẽ là cách tốt nhất để đảo ngược MSB < -> LSB của bất kỳ chiều dài sử dụng XOR trong vòng lặp for

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 

Answer 5

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)