Laden...

[Artikel] Bitoperationen in C#

Erstellt von egrath vor 16 Jahren Letzter Beitrag vor 14 Jahren 78.096 Views
egrath Themenstarter:in
871 Beiträge seit 2005
vor 16 Jahren
[Artikel] Bitoperationen in C#

Bitoperatoren in C#

Üblicherweise arbeitet man während der Entwicklung mit C# mit dem Byte als kleinste logische Einheit. Ab und an ist es aber nötig auf einer noch kleineren Ebene arbeiten zu können, beispielsweise wenn man mittels P/Invoke auf nativen Code zugreift und vom diesen Daten zurückbekommt die Informationen auf Bitebene enthalten.

Genau hier kommen die Bit Operatoren ins Spiel. Untenstehend eine übersicht über diese:*OR *AND *NOT *XOR *Shifting

Der Artikel beinhaltet folgende Bereiche:*Übersicht und beschreibung der einzelnen Operatoren *Anwendungsfälle *Endianess von Systemen

OR

Der OR Operator verknüpft zwei Werte, bei denen das Ergebnis nur dann 1 ist wenn wenn einer der beiden (oder aber beide) Werte 1 ist. Andernfalls ist das Ergebnis 0. Grafische darstellung:

In C# ist der entsprechende Operator das Pipe ("|"). Codebeispiel:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205                   = 11001101
        byte b2 = 0x6A; // 0x6A = 106                   = 01101010

        byte erg1 = ( byte ) ( b1 | b2 ); // 0xEF = 239 = 11101111
        Console.Out.WriteLine( "{0:X2}", erg1 );

        int i1 = 37841; // 0x93D1                           = 00000000000000001001001111010001
        byte b3 = b2; // 0x6A = 106                         = 00000000000000000000000001101010
        int erg2 = ( int ) ( i1 | b3 ); // 0x93FB = 37883   = 00000000000000001001001111111011
        Console.Out.WriteLine( "{0:X}", erg2 );
    }
}

AND

Der AND Operator verknüpft zwei Werte, bei denen das Ergebnis dann 1 ist, wenn beide Eingangswerte 1 sind. Andernfalls ist das Ergebnis 0. Grafische darstellung:

In C# ist der entsprechende Operator das Ampersand ("&"). Codebeispiel:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205                   = 11001101
        byte b2 = 0x6A; // 0x6A = 106                   = 01101010

        byte erg1 = ( byte ) ( b1 & b2 ); // 0x48 = 72  = 01001000
        Console.Out.WriteLine( "{0:X2}", erg1 );

        int i1 = 37841; // 0x93D1                           = 00000000000000001001001111010001
        byte b3 = b2; // 0x6A = 106                         = 00000000000000000000000001101010
        int erg2 = ( int ) ( i1 & b3 ); // 0x40 = 64        = 00000000000000000000000001000000
        Console.Out.WriteLine( "{0:X}", erg2 );
    }
}

NOT

Der NOT Bitoperator ist der einzige, welcher nur den Quellwert für seine Arbeit benötigt (Unärer Operator). Er "dreht" im Prinzip alle Bits genau auf den Gegenwert um (aus 0 wird 1 und umgekehrt). Grafische Darstellung:

In C# ist der entsprechende Operator die Tilde ("~"). Codebeispiel:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205                   = 11001101
        byte b2 = 0x6A; // 0x6A = 106                   = 01101010

        Console.Out.WriteLine( "{0:X8}", b1 );  // 0x000000CD = 00000000000000000000000011001101
        Console.Out.WriteLine( "{0:X8}", b2 );  // 0x0000006A = 00000000000000000000000001101010

        Console.Out.WriteLine( "{0:X8}", ~b1 ); // 0xFFFFFF32 = 11111111111111111111111100110010
        Console.Out.WriteLine( "{0:X8}", ~b2 ); // 0xFFFFFF95 = 11111111111111111111111110010101
    }
}

Aus diesem Beispiel heraus erfährt man wieder ein kleines Detail:*Bitoperationen werden immer als Int32 (oder Int64; je nachdem wie gross der Ausgangsdatentyp ist) ausgeführt, dementsprechend ist auch das Ergebnis der Operation wie man an der Ausgabe des obigen Codes sehen kann.

Manch einer mag sich jetzt vielleicht fragen: Ist der NOT Bitoperator wirklich der einzige Unäre Bitoperator? (Wie oben ausgesagt)
Darüber lässt sich nun streiten. So wie die Tilde das Einerkomplement berechnet, so berechnet das Minus das Zweierkomplement. Es ist allerdings die Frage ob man das Minus als Bitoperation oder als Arithmetische Operation ansieht. Ich würde das Minus als Zwitter zwischen diesen beiden sehen.

XOR

Was aber nun, wenn man zwei Werte so miteinander verknüpfen möchte, dass das Ergebnis nur dann 1 ist wenn entweder die Quelle oder das Pattern 1 ist, nicht aber beider oder gar keines? Grafisch dargestellt also:

In der boolschen Algebra gibt es kein Exklusives Oder (XOR) man muss sich daher folgenden Konstruktes bemühen:

ERGEBNIS = NOT(( A AND B ) OR (( NOT A ) AND ( NOT B )))

In C# geschrieben sieht dass dan so aus:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205            = 11001101
        byte b2 = 0x6A; // 0x6A = 106            = 01101010

        byte b3 = ( byte ) ~(( b1 & b2 ) | (( ~b1 ) & ( ~b2 )));
        Console.Out.WriteLine( "{0:X}", b3 );
    }
}

Wie man sehen kann, ein relativ umständlicher Weg. Als Lösung springt hier der XOR Operator, welcher in C# durch das Karet ("^") dargestellt wird ein. Mit diesem vereinfacht sich das ganze auf:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205            = 11001101
        byte b2 = 0x6A; // 0x6A = 106            = 01101010

        byte b3 = ( byte ) ( b1 ^ b2 );
        Console.Out.WriteLine( "{0:X}", b3 );
    }
}

Untenstehend noch ein komplettes Codebeispiel, welches auch noch einige andere Dinge zeigt die danach gleich besprochen werden:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205                   = 11001101
        byte b2 = 0x6A; // 0x6A = 106                   = 01101010

        byte erg1 = ( byte ) ( b1 ^ b2 ); // 0xA7 = 167 = 10100111
        int  erg2 = ( b1 ^ b2 );          // 0xA7 = 167 = 000000000000000000000010100111
        Console.Out.WriteLine( "{0:X2}", erg1 );

        int i1 = 37841; // 0x93D1                           = 00000000000000001001001111010001
        byte b3 = b2; // 0x6A = 106                         = 00000000000000000000000001101010
        int erg3 = ( int ) ( i1 ^ b3 ); // 0x93BB = 37819   = 00000000000000001001001110111011
        Console.Out.WriteLine( "{0:X}", erg3 );
    }
}

Im obigen Beispiel kann man einige grundlegende Dinge von Bitoperationen sehen:*Es ist nicht zwingend notwendig dass die beiden zu verknüpfenden Daten vom selben Typ sind. Wenn man wie oben beispielsweise einen int (32 Bit breit; Wird zu System.Int32 im CIL) mit einem byte (8 Bit breit; Wird zu System.Byte im CIL) verknüpft, so werden die nicht benutzten stellen mit 0 aufgefüllt. *Das Ergebnis einer Bitoperation ist immer ein int. Man muss also bei zuweisungen casten, sofern kein Operatorüberladung für den entsprechenden, impliziten cast existiert.

Vielleicht fragt sich der eine oder andere nun, warum die Repräsentation der Bytes so ist wie sie ist und nicht andersrum: Das hat etwas mit der sg. Endianess eines Systems zu tun. Weiter unten findet sich ein entsprechender Teil welcher erklärt was dies ist und warum es für uns wichtig ist.

SHIFTING

Beim Shifting wird die Bitreihenfolge des Eingangswerts entweder nach links ("<<") oder nach rechts (">>") um einen angegebenen Wert verschoben. Die resultierende Lücke wird dabei mit 0 aufgefüllt. Grafische darstellung:

Wenn man also nun z.b. einen Shift um 8 nach rechts durchführt so ist bei einem Byte das Ergebnis immer 0. Analog dazu wenn der Shift nach links durchgeführt wurde, da dann an der rechten Seite eine 0 eingefügt wird.

In C# ist der Operator für das Shifting das doppelte Größer- oder Kleinerzeichen (">>", "<<") gefolgt von einer Nummer die die Anzahl des Shifts festlegt. Codebeispiel:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        byte b1 = 0xCD; // 0xCD = 205       = 11001101
        byte b2, b3, b4, b5;

        b2 = ( byte ) ( b1 << 1 );  // 0x9A = 10011010
        b3 = ( byte ) ( b1 << 2 );  // 0x34 = 00110100
        b4 = ( byte ) ( b1 << 3 );  // 0x68 = 01101000
        b5 = ( byte ) ( b1 << 8 );  // 0x00 = 00000000

        Console.Out.WriteLine( "{0:X2} {1:X2} {2:X2} {3:X2}", b2, b3, b4, b5 );

        b2 = ( byte ) ( b1 >> 1 ); // 0x66 = 01100110
        b3 = ( byte ) ( b1 >> 2 ); // 0x33 = 00110011
        b4 = ( byte ) ( b1 >> 3 ); // 0x19 = 00011001
        b5 = ( byte ) ( b1 >> 8 ); // 0x00 = 00000000

        Console.Out.WriteLine( "{0:X2} {1:X2} {2:X2} {3:X2}", b2, b3, b4, b5 );
    }
}

Das Shifting kann auf jeden Werttyp angewandt werden, welcher Ganzzahlen speichert. Strukturen (welche ja auch Wertetypen sind) und Fließkommazahlen (Decimal, Float, Double) können nicht geshiftet werden. Der Grund liegt darin:*Bei Strukturen würde es grundsätzlich keinen Sinn machen. *Fließkommazahlen sind auf Bitebene im IEE754 Format gespeichert. Ein Shifting würde zu sinnlosen Werten führen, dementsprechend wird es unterbunden.

Anwendungsbeispiele

Für was kann man das ganze nun denn gebrauchen? Beispielsweise kommt es manchmal vor, dass eine native Applikation welche mittels P/Invoke aufgerufen wird ein sg. "Bit-Feld" zurückgibt, welches die einzelnen Bits als True und False Flags benutzt (da es unter C/C++ mittels eines Sprachkonstruktes leicht möglich ist eine Stuktur zu definieren deren einzelne Felder Bitpositionen darstellen). Stellen wir uns folgendes Bitfeld vor:

Diese bekommen wir von der nativen Methode zurückgeliefert und wollen nun feststellen ob "Flag 1" gesetzt ist oder nicht. Dazu können wir beispielsweise folgendes Konstrukt verwenden:


using System;

public class Test
{
    private static byte FLAG_1 = 0x04; // 00000100
    private static byte FLAG_3 = 0x01; // 00000001

    public static void Main( string[] args )
    {
        byte bitfield = 0x05; // 00000101

        if(( bitfield & FLAG_1 ) == FLAG_1 )
            Console.Out.WriteLine( "Flag 1 gesetzt!" );

        if(( bitfield & ( FLAG_1 | FLAG_3 )) == ( FLAG_1 | FLAG_3 ))
            Console.Out.WriteLine( "Flag 1 und 3 sind gesetzt!" );
    }
}

Auch wenn der Code auf den ersten Blick etwas verwirrend wirkt, so werden wir die Logik dahinter doch gleich feststellen wenn wir diesen im Kopf durchgehen und die einzelnen Operationen durchrechnen. Wenn wir einer nativen Methode ein Bitfeld übergeben müssen, können wir auch dies mit unseren Bit-Operationen erstellen. Wir wollen beispielsweise ein Bitfeld übergeben bei dem "Flag 1" und "Flag 2" gesetzt sind:


using System;

public class Test
{
    private static byte FLAG_1 = 0x04; // 00000100
    private static byte FLAG_2 = 0x01; // 00000001

    public static void Main( string[] args )
    {
        byte bitfield = 0x00;

        bitfield |= FLAG_1;
        bitfield |= FLAG_2;

        Console.Out.WriteLine( "{0:X2}", bitfield );

        // Alternativ: Beide gleichzeitig setzen
        bitfield = 0x00;
        bitfield |= ( byte ) ( FLAG_1 | FLAG_2 );
        Console.Out.WriteLine( "{0:X2}", bitfield );
    }
}

Ausser dem oben genannten beispiel gibt es noch einige andere Bereich der Anwendung. So kann man mittels eines Bitshiftings relativ schnell multiplizieren, wenn der Multiplikator ein Wert aus dem Bereich 2^n ist. Beispiel:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        int val = 7384;

        for( int i = 1; i < sizeof( int ) * 8; i ++ )
        {
            Console.Out.WriteLine( "{0} x {1} = {2}",
                val,
                1 << i,
                val << i );
        }
    }
}

Ob das ganze nun auch wirklich schneller ist kann heutzutage nicht mehr klar beantwortet werden. In C/C++ Zeiten und mit noch nicht so ausgereiften Compilern konnte das ganze klar mit einem Ja beantwortet werden, da ein SHL (Shift Left für Multiplikation) bzw. ein SHR (Shift Right für Division) schneller ausgeführt wurde als ein MUL oder DIV. Heutige Compiler optimieren extremst und es ist nicht auszuschliessen dass eine Multiplikation oder Division bei der der Multiplikator oder Divisor im Bereich von 2^n liegt nicht auf diese Weise umgesetzt wird.

Interessierte können sich mittels Bitoperatoren auch die Struktur von Werttypen (alle welche Zahlen speichern, also keine Strukturen) anzeigen lassen:


using System;

public class Test
{
    public static void Main( string[] args )
    {
        int val = -8;

        DumpValue( val );
    }

    private static void DumpValue( int val )
    {
        int bits = System.Runtime.InteropServices.Marshal.SizeOf( val ) * 8;

        Console.Out.WriteLine( "Type      : {0}", val.GetType().ToString() );
        Console.Out.WriteLine( "Bit width : {0}", bits );

        uint bitTest = 0x80000000;
        for( int index = 0; index < bits; index ++ )
        {
            if(( val & bitTest ) == bitTest )
                Console.Out.Write( "1" );
            else
                Console.Out.Write( "0" );

            bitTest = bitTest >> 1;
        }
        Console.Out.WriteLine();
    }
}

Endianess von Systemen

Auch wenn es nicht direkt etwas mit Bitoperationen zu tun hat, so soll nun doch auch noch eine Kleinigkeit aus den tiefen des Systems beleuchtet werden: Die Endianess

Diese sagt aus, in welcher Binärform ein Wert dargestellt wird: Das niederwertigste Byte zuerst (Little Endian) oder das höchstwertigste Byte zuerst (Big Endian). Eine kleine Grafik veranschaulicht dies:

Vermutlich wird uns Big Endian vertrauter sein, da dies auch unserem natürlichem Umgang mit Zahlen entspricht. Ein Problem in welches wir aber tapsen können ist, wenn wir Daten aus einem System erhalten welches nicht unserer Endianess entspricht. Die .NET CLR verwendet standardmässig immer Little Endian auf allen Platformen (ausgenommen dem XNA Framework auf der XBox360, da haben wir Big Endian...).

Es ist zu beachten, dass es sich bei der Endianess nur um die Position der Bytes innerhalb eines Datenwerts handelt, die Position der einzelnen Bits innerhalb des Bytes sind bei beiden gleich:

Wenn wir also beispielsweise einen Int32 als Binärwert in ein File schreiben lassen und dann im XNA Framework auch wieder Binär auslesen und in einen Int32 konvertieren so erhalten wir einen falschen Wert für diesen (Falsch eigentlich nicht, nur passen eben die Bytepositionen nicht). Wir müssen uns daher einen entsprechenden Konverter schreiben, damit wir diese Bytes wieder in Ihre richtige Position rücken. Eine Hilfsklasse dafür ist "System.BitConverter", welcher ein byte Array entgegennimmt und dieses in einen anderen Werttype verwandelt. Der umgekehrte Weg (von Werttypen nach Byte Array) geht natürlich mit der Klasse ebenso.

Am schluss möchte ich noch folgenden Personen für das Korrekturlesen und das geben von Anregungen danken (in alphabetischer Reihenfolge):*hauptmann *herbivore *norman_timo *Peter Bucher *Programmierhans *SimonKnight6600 *svenson *talla

Hinweis von herbivore vor 11 Jahren

Hier noch ein inhaltlicher Nachtrag:

egrath nennt die Operanden Pattern, den ersten Operanden Quell-Pattern, den zweiten Operanden je nach Operation AND-, OR- oder XOR-Pattern. In der Praxis ist der erste Operand oft eine Variable und der zweite oft ein (festes oder berechnetes) Bitmuster, welches dazu dient, bestimmte Bits aus dem Quell-Pattern zu setzen, zu löschen, zu negieren oder abzufragen. Ein Bitmuster, das diesen Zweck erfüllt, wird Maske (englisch Mask) genannt und das Anwenden der Maske auf einen Wert maskieren.

915 Beiträge seit 2006
vor 16 Jahren

Super Artikel 👍

Wie vernichtet stand Andreas unter den flammenden Augen seiner Kunden.
Ihm war's, als stünde des Schicksals dunkle Wetterwolke über seinem Haupte X(

D
10 Beiträge seit 2007
vor 16 Jahren

Super! 👍

4 Beiträge seit 2008
vor 15 Jahren

vielen dank fuer diesen super artikel!

regards,
buk

52 Beiträge seit 2007
vor 15 Jahren

Der Artikel ist sagenhaft und sehr brauchbar wenn es um Bitmanipulationen geht, 1000 Dank dafür! best story in town! 8)

yb~~~~~~~~~~~~

1.002 Beiträge seit 2007
vor 14 Jahren

Hall egrath,

sagenhaft! Vielen Dank für den Artikel!

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

479 Beiträge seit 2008
vor 14 Jahren

Hallo,

extrem guter, hilfreicher Artikel, 👍 👍

mfg.
markus111

[Follow me on Twitter](http://twitter.com/blendingsky)
256 Beiträge seit 2006
vor 14 Jahren

Vielen Dank für die Arbeit!! Druck ich mir aus und Pins an die Wand..