Bitfelder in C #

Question

Also, bitfields. Insbesondere großes bitfields. Ich verstehe, wie in einem Bitfeld einzelne Werte zu manipulieren, aber wie würde ich mich über das tut dies auf einem großen Satz, wie sagen:

uint[] bitfield = new uint[4] { 0x0080000, 0x00FA3020, 0x00C8000, 0x0FF00D0 };

Das spezifische Problem, das ich habe ist, Tun linke und rechte Verschiebungen, die durch über die gesamte Array tragen. So zum Beispiel, wenn ich ein >> 4 auf dem oben genannten Array tue, würde ich am Ende mit:

uint[4] { 0x0008000, 0x000FA302, 0x000C800, 0x00FF00D };

Nun wird ein (zu) stark vereinfachten Algorithmus hier aussehen könnte etwas (das ich Code on the fly writting):

int shift = 4;
for (int i = 0; i <= shift; i++) {
    for (int j = bitfield.GetUpperBound(0); j > 0; j--) {
        bitfield[j] = bitfield[j] >> 1;
        bitfield[j] = bitfield[j] + ((bitfield[j-1] & 1) << (sizeof(uint)*8));
    }
    bitfield[0] = bitfield[0] >> 1;
}

Gibt es etwas, dass gebaut könnte mit dieser Art von Daten erleichtern arbeiten?

Answer 1

Was macht Sie denken, dass BitArray bools intern verwendet? Es verwendet Boolesche Werte, die Bits in Bezug auf die API zu repräsentieren, aber unter der Haube Ich glaube, es ein int verwendet [].

Answer 2

Ich bin mir nicht sicher, ob es der beste Weg, es zu tun, aber das könnte funktionieren (Verschiebungen beschränke 0-31 im Bereich sein.

    public static void ShiftLeft(uint[] bitfield, int shift) {

        if(shift < 0 || shift > 31) {
            // handle error here
            return;
        }

        int len = bitfield.Length;
        int i = len - 1;
        uint prev = 0;

        while(i >= 0) {
            uint tmp        = bitfield[i];
            bitfield[i] = bitfield[i] << shift;
            if(i < len - 1) {
                bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
            }
            prev = tmp;

            i--;
        }

    }

    public static void ShiftRight(uint[] bitfield, int shift) {

        if(shift < 0 || shift > 31) {
            // handle error here
            return;
        }
        int len = bitfield.Length;
        int i = 0;
        uint prev = 0;

        while(i < len) {
            uint tmp        = bitfield[i];
            bitfield[i] = bitfield[i] >> shift;
            if(i > 0) {
                bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
            }
            prev = tmp;

            i++;
        }

    }

PD: Mit dieser Änderung sollten Sie in der Lage sein, Veränderungen zu handhaben mehr als 31 Bits. Könnte Refactoring, um es etwas weniger hässlich aussehen, aber in meinen Tests, es funktioniert und es scheint nicht so schlecht Performance-weise (es sei denn, es gibt tatsächlich etwas gebaut in großen Bitsets zu handhaben, was der Fall sein könnte).

    public static void ShiftLeft(uint[] bitfield, int shift) {

        if(shift < 0) {
            // error
            return;
        } 

        int intsShift = shift >> 5;

        if(intsShift > 0) {
            if(intsShift > bitfield.Length) {
                // error
                return;
            }

            for(int j=0;j < bitfield.Length;j++) {
                if(j > intsShift + 1) {     
                    bitfield[j] = 0;
                } else {
                    bitfield[j] = bitfield[j+intsShift];
                }
            }

            BitSetUtils.ShiftLeft(bitfield,shift - intsShift * 32);
            return;
        }

        int len = bitfield.Length;
        int i = len - 1;
        uint prev = 0;

        while(i >= 0) {
            uint tmp    = bitfield[i];
            bitfield[i] = bitfield[i] << shift;
            if(i < len - 1) {
                bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
            }
            prev = tmp;

            i--;
        }

    }

    public static void ShiftRight(uint[] bitfield, int shift) {

        if(shift < 0) {
            // error
            return;
        } 

        int intsShift = shift >> 5;

        if(intsShift > 0) {
            if(intsShift > bitfield.Length) {
                // error
                return;
            }

            for(int j=bitfield.Length-1;j >= 0;j--) {
                if(j >= intsShift) {        
                    bitfield[j] = bitfield[j-intsShift];
                } else {
                    bitfield[j] = 0;
                }
            }

            BitSetUtils.ShiftRight(bitfield,shift - intsShift * 32);
            return;
        }


        int len = bitfield.Length;
        int i = 0;
        uint prev = 0;

        while(i < len) {
            uint tmp    = bitfield[i];
            bitfield[i] = bitfield[i] >> shift;
            if(i > 0) {
                bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
            }
            prev = tmp;

            i++;
        }

    }

Answer 3

Erweiterungsmethoden verwenden, könnten Sie dies tun:

public static class BitArrayExtensions
{
    public static void DownShift(this BitArray bitArray, int places)
    {
        for (var i = 0; i < bitArray.Length; i++)
        {
            bitArray[i] = i + places < bitArray.Length && bitArray[i + places];
        }
    }

    public static void UpShift(this BitArray bitArray, int places)
    {
        for (var i = bitArray.Length - 1; i >= 0; i--)
        {
            bitArray[i] = i - places >= 0 && bitArray[i - places];
        }
    }
}

Leider konnte ich nicht mit einer Art und Weise kommen die Shift-Operatoren zu überlasten. (Vor allem, weil BitArray abgedichtet ist.)

Wenn Sie beabsichtigen, ints oder uints zu manipulieren, können Sie Erweiterungsmethoden schaffen für die Bits in / Extrahieren von Bits aus dem BitArray Einfügen. (BitArray hat einen Konstruktor, der eine Reihe von ints nimmt, sondern dass man nur den Ball zu weit).

Answer 4

Dies bezieht sich nicht speziell verschoben wird, könnte aber für die Arbeit mit großen Mengen nützlich sein. Es ist in C, aber ich denke, es könnte leicht zu C # angepasst werden

Gibt es eine praktische Grenze auf die Größe von Bitmasken?