myCSharp.de - DIE C# und .NET Community (https://www.mycsharp.de/wbb2/index.php)
- Knowledge Base (https://www.mycsharp.de/wbb2/board.php?boardid=68)
-- Artikel (https://www.mycsharp.de/wbb2/board.php?boardid=69)
--- [Artikel] Bitoperationen in C# (https://www.mycsharp.de/wbb2/thread.php?threadid=48671)


Geschrieben von egrath am 21.12.2007 um 09:30:
  [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:Der Artikel beinhaltet folgende Bereiche: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:

C#-Code:
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:

C#-Code:
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:

C#-Code:
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: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:

C#-Code:
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:

C#-Code:
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:

C#-Code:
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: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:

C#-Code:
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: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:

C#-Code:
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:

C#-Code:
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:

C#-Code:
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:

C#-Code:
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):


Geschrieben von Andreas.May am 21.12.2007 um 10:58:
 
Super Artikel Daumen hoch


Geschrieben von DriZit am 26.02.2008 um 17:35:
 
Super! Daumen hoch


Geschrieben von buk am 11.09.2008 um 12:55:
 
vielen dank fuer diesen super artikel!

regards,
buk


Geschrieben von yetibrain am 02.02.2009 um 15:35:
 
Der Artikel ist sagenhaft und sehr brauchbar wenn es um Bitmanipulationen geht, 1000 Dank dafür! best story in town! cool


Geschrieben von m0rius am 03.07.2009 um 10:36:
 
Hall egrath,

sagenhaft! Vielen Dank für den Artikel!

m0rius


Geschrieben von markus111 am 21.01.2010 um 16:17:
 
Hallo,

extrem guter, hilfreicher Artikel, Daumen hoch Daumen hoch

mfg.
markus111


Geschrieben von camelord am 04.03.2010 um 10:39:
 
Vielen Dank für die Arbeit!! Druck ich mir aus und Pins an die Wand..


© Copyright 2003-2019 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 24.08.2019 18:46