Du bist nicht angemeldet.

meschi

Fortgeschrittener

  • »meschi« ist der Autor dieses Themas

Beiträge: 263

Registrierungsdatum: 23.08.2011

Wohnort: /

Danksagungen: 40

  • Private Nachricht senden

1

01.11.2011, 00:05

C/C++ Binäre Operationen

Ein Merkmal,
das C hat, welches es sicherlich von manchen anderen Sprachen abhebt ist der grundlegende einbau von binären Operatoren.
Ich rede hier von Operatoren wie z.B. << (bitshifting), & (binäres und), | (binäres oder), ^ (binäres xor), ~(binäre negation).
Oft reden Leute, die ich kenne davon wie als wäre das irgendein unerlernbares Profi-Wissen. Da solche Sachen öfters verwendet werden, was man zum Beispiel beim Code-lesen bemerkt, will ich hier ein kleines Tutorial entstehen lassen für die, die es nicht können. Ich werde später zum Beispiel auch zeigen wie man Bits mit diesen Operatoren und bitmasken setzt. Ich finde die Idee interessant dieses Tutorial diskussionsartig zu gestalten. Das heißt, ich fange an und wenn einer etwas hinzufügen möchte soll er das auch bitte tun. So kann zu diesem sehr hilfreichen Thema ein immer besseres Tutorial entstehen.
Ich gehe jetzt anfangs davon aus, dass potentielle Leser mit binären, dezimalen und vielleicht hexadezimalen zahlensystemen vertraut sind.

Ich fange jetzt einfach mal mit dem Operator "<<"/">>" an.
Diese beiden Operatoren werden für das so genannte bit-shifting verwendet.
Da Zahlen hardwareintern binär dagestellt werden sieht eine zufällige Zahl beispielsweise so aus:
00101101
Diese Zahl entspricht der 45 im Dezimalsystem.

Wenn wir also beispielsweise eine Integer-variable mit dem wert 45 definieren

C/C++-Quelltext

1
int number = 45;

dann wird diese 45 im Arbeitsspeicher wie oben dargestellt.
Wenn wir jetzt den Bitshifting-operator "<<" darauf anwenden könnte es so aussehen:

C/C++-Quelltext

1
number << 1;


Mit dieser Zeile Code schieben wir die bits einfach um eins nach links (in Richtung der Pfeile)
Dann würde diese Zahl im Speicher nun so aussehen:
01011010
Mit der Zeile

C/C++-Quelltext

1
number << 2;


würden wir die bits um zwei stellen weiter nach links "shiften".
Jetzt fällt aber etwas auf:
Wir schieben nämlich eine eins "heraus".
Das ist tatsächlich so.
Bei einer 8 bit zahl würden wir jetzt tatsächlich die eins rausschieben. diese eins geht verloren. Die Zahl sähe im Speicher dann so aus:
01101000
Dieses Shiften können wir auch umkehren:

C/C++-Quelltext

1
number >> 3;


würde die bits wieder an die ursprüngliche Stelle zurückshiften. Die Zahl sähe binär dann so aus:
00001101
Wenn wir jetzt den Wert mit dem Anfangswert vergleichen (13 <-> 45), dann sehen wir, dass wir einen Datenverlust haben. Die Einsen wurden herausgeshiftet. Es werden die frei gewordenen Zeichen beim Shiften durch Nullen gefüllt.
Jetzt habt ihr sicher die Frage, wozu dieses Shiften denn sinnvoll ist.
Das ist einfach erklärt:
Bei Multiplikationen. Wenn man eine Zahl mit zweierpotenzen multipliziert, kann man um den Exponent nach links shiften. Veranschaulicht ist das dann so:
x * 2¹ entspricht x << 1
x * 2² entspricht x << 2
x * 2³ entspricht x << 3
Das lässt sich durch das Binäre Zahlensystem erklären. Da es auf der Basis Zwei arbeitet bedeutet jede neue stelle im Prinzip, dass der darstellbare Wertebereich um zwei Multipliziert wird. Zur erinnerung: 2¹ entspricht 1 bit (zwei Zustände darstellbar), 2² entsprechen 2 bit (vier Zustände darstellbar) usw.
wenn man also hinten ein bit hinzufügt wird die dargestellte Menge um den Faktor 2 größer (da ja ein bit zwei zustände hat).
Hier möchte ich noch zwei Sachen anmerken und betonen:
1. Der Datentyp muss groß genug sein (ihr dürft keine gesetzten bits (mit wert 1) herausshiften)
2. Bitshifting geht NUR mit Zweierpotenzen

Wieso benutzt man dann nicht gleich eine einfache Multiplikation?
Auf Hardwareebene werden Multiplikationen in Additionen aufgeteilt. Da das bei weitem mehr Taktzyklen verbraucht als einfaches Bitshifting ist Bitshifting um einiges schneller als eine "echte" Multiplikation. Hier muss man fairerweise anmerken, dass moderne Compiler diesbezüglich automatisch optimieren. Aber dieses Wissen kann trotzdem nicht schaden.
Genau so verhält es sich mit der Division, nur dass nach rechts geshiftet wird. hierbei sind die Punkte 1 & 2 immer noch zu beachten. Hier sei nochmal wiederholt, dass herausshiften von Einsen Datenverlust bedeutet.


Das binäre oder ist relativ einfach erklärt. Dargestellt wird es durch einen Senkrecht-strich "|"
Dieses und wird in C und C++ für die Binäre Oder-operation verwendet.
Sie funktioniert wie folgt: Es werden zwei Datenmengen bitweise verglichen und an jeder stelle wo ENTWEDER eins ODER beide bits den Wert 1 haben hat das Ergebniss auch den Wert 1.
Das sieht dann so aus:
01010010
|00111001
------------------
01111011

Bei der Operation kommt ein Ergebnis heraus, dass aus den zwei Edukten (Ausgangsdaten) erzeugt wird. Hier merke ich noch an, dass man es wie in C so toll üblich mit dem = Operator verknüpfen kann.
also könnte man z.b. das machen:

C/C++-Quelltext

1
2
char abc = 01001011b; /*ein char ist ein byte groß*/
abc |= 01100110b;

abc sähe dann binär so aus:
0110111

Dieser kombinierte "=" Operator ist übrigends mit allen bitweisen Operatoren möglich.

Das binäre XOR (^) funktioniert wie das binäre |, nur ist das ergebnis 1 wenn genau eins der zwei ausgangsbits 1 ist.
Alle anderen Fälle ergeben null.
10001010
^ 10010111
-------------------
00011101
Aus dem Ergebnis kann man durch das zweite Edukt wieder das erste "errechnen". Deshalb gehen bei XOR keine Informationen verloren.
Durch diese verlustfreie Konvertierung kann (und wird) XOR oft in Kryptosystemen eingesetzt werden. (Beispiele: AES, DES, Blowfish, ...)
Dabei ist Edukt 1 der plain text, das heißt der unverschlüsselte Text. Das Edukt 2 dient als key bzw. Schlüssel. Das Ergebnis ist die chiffrierte Nachricht.

Binäre Negation (~) funktioniert im Prinzip auch ganz simpel:
~10101010011=01010101100
Hier werden alle Bits "umgedreht".

Bits setzen und bits löschen
Man kann Bits auf verschiedene weisen setzen und löschen.
Wir haben jetzt zum Beispiel die Bitreihe:
11111111
und wollen das dritte bit (von rechts) löschen.
Das kann man auf unterschiedliche Weisen implementieren.

C/C++-Quelltext

1
2
3
4
5
//GCC-Syntax
//Variante 1
char ergebnis = 0b11111111 & 0b11111011;//einfachste variante
//Variante 2
char ergebnis2 = 0xFF & ~(0x1 << 2);//übliche variante

Anmerkung: 0xFF ist Hexadezimal und entspricht 11111111 binär
Bits setzen:
Hier setzte ich das dritte bit auf zwei unterschiedliche weisen

C/C++-Quelltext

1
2
char ergebnis = 0x00 | (0x1 << 2);
char ergebnis = 0x00 | 0b00000100; //bzw 0x00 | 0x04


Bei den gezeigten Vorgehensweisen wird das Bit in jedem Fall gesetzt, also auch wenn es schon gesetzt ist.
Man kann mittels XOR auch einzelne Bits umdrehen:
Hier drehe ich das dritte bit um

C/C++-Quelltext

1
char ergebnis = 0x00 ^ (0x1 << 2);



Ich hoffe dieses Tutorial wird Anfängern oder Neulingen auf diesem Gebiet ein bischen helfen :)
Wenn ihr noch Wünsche oder Vorschlägt habt, bitte bitte schreibt das!
LG,
meschi

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »meschi« (22.02.2012, 19:45)


Es hat sich bereits 1 registrierter Benutzer bedankt.

Benutzer, die sich für diesen Beitrag bedankt haben:

Alex (01.11.2011)

Alex

Fortgeschrittener

Beiträge: 372

Registrierungsdatum: 23.06.2011

Wohnort: /home/alex

Danksagungen: 117

  • Private Nachricht senden

2

01.11.2011, 19:35

Du hast oben das binäre und & mit dem binären oder | verwechselt:

1&1 <=> 1
1&0 <=> 0
0&1 <=> 0
0&0 <=> 0

aber

1|1 <=> 1
1|0 <=> 1
0|1 <=> 1
0|0 <=> 0

und du hast einen Zeilenumbruch vergessen, nämlich bei


also könnte man z.b. das machen:

C/C++-Quelltext

1
char abc = 01001011b; //ein char ist ein byte großabc &= 01100110b;

abc sähe dann binär so aus:
0110111


das sollte wahrsch

C/C++-Quelltext

1
2
char abc = 01001011b;
abc &= 01100110b;


außerdem wäre das dann (wie vorhin begründet) 01000010b..

aber sonst: dankeschön, das kann ein nützliches Tut werden! :-)
alexthinking.com - yet another computer weblog

Zitat

Chuck Norris knows the state of schroedinger's cat.

Es haben sich bereits 2 registrierte Benutzer bedankt.

Benutzer, die sich für diesen Beitrag bedankt haben:

Patrick (01.11.2011), meschi (02.11.2011)

meschi

Fortgeschrittener

  • »meschi« ist der Autor dieses Themas

Beiträge: 263

Registrierungsdatum: 23.08.2011

Wohnort: /

Danksagungen: 40

  • Private Nachricht senden

3

02.11.2011, 23:05

bei der zeile mit dem &= haut er mir iwie den zeilenumbruch raus :<

Hehe ja es ist mir heute in der schule eigefallen, dass ich doch tatsächlich & und | verwechselt hab :thumbsup:

meschi

Fortgeschrittener

  • »meschi« ist der Autor dieses Themas

Beiträge: 263

Registrierungsdatum: 23.08.2011

Wohnort: /

Danksagungen: 40

  • Private Nachricht senden

4

22.02.2012, 19:46

So, ich hab jetzt das Tutorial um die fehlenden Elemente geupdated.
LG,
meschi

meschi

Fortgeschrittener

  • »meschi« ist der Autor dieses Themas

Beiträge: 263

Registrierungsdatum: 23.08.2011

Wohnort: /

Danksagungen: 40

  • Private Nachricht senden

5

23.02.2012, 22:46

Fehlt euch noch was?