BOOLESCHE ALGEBRA: HAUSAUFGABE 11 IN 2 BZW. 3 ZEILEN!
Mehr als 2 bzw. 3 Zeilen für die Funktionen der Zweierkomplement-Programmieraufgabe in HA 12 gebraucht? Klar, die Musterlösung auch. Viel mehr. Aber mit dem Wissen von Tutorium 13 lässt sich die Aufgabenstellung auch in wenigen Zeilen lösen. Dazu bedienen wir uns nämlich einfach den Bitweise-Operatoren, die uns eigentlich gar nicht unbekannt sind seit den Zweierkomplementzahlen.
Was haben wir da gemacht? Bei der Rückumwandlung von der 2K-Darstellung in Dezimal konnte man die Umwandlungsschritte ja entweder einfach rückwärts gehen, oder mit dieser eleganten, allgemeingültigen Methode mit XOR die Zahl umrechnen. Zur Erinnerung zeige ich beides nochmal: Schauen wir uns eine positive, 01010101 und eine negative 11001010 8 Bit 2K-Zahl an.
Für Die negative Zahl gilt:
(1) Schritte Rückwärts:
Ursprüngliche Zahl: 11001010 -------- Negativ -> Invertieren: 00110101 1 addieren: 00000001 -------- Ergebnis: 00110110
(2) XOR mit VZB, VZB addiert:
Ursprüngliche Zahl: 11001010 Vorzeichenbit (1) 8 Bit: 11111111 -------- XOR mit Vorzeichenbit (1) 00110101 Vorzeichenbit addieren (1) 00000001 -------- Ergebnis: 00110110
Für Die Positive Zahl gilt:
(1) Schritte Rückwärts:
Ursprüngliche Zahl: 01010101 -------- Pos. -> Nicht invertieren: 01010101 Nix addieren: 01010101 -------- Ergebnis: 01010101
(2) XOR mit VZB, VZB addiert:
Ursprüngliche Zahl: 01010101 Vorzeichenbit (0) 8 Bit: 11111111 -------- XOR mit Vorzeichenbit (0) 01010101 Vorzeichenbit addieren (0) 00000000 -------- Ergebnis: 01010101
Hey! Beide Methoden machen irgendwie effektiv das gleiche... oder? Würde man es aber in C/C++ schreiben, könnte man (1) nur mit einer Fallunterscheidung (if-Abfrage) lösen; (2) würde einfach in einem Durchlauf, ohne Unterbrechnung funktionieren. (2) macht man als effizienter Etechniker also lieber.
Im Tutorium haben wir, um die XOR-Verknüpfung zu realisieren, genau einfach bitweise unser Ergebnis berechnet. Was heißt bitweise? Bitweise ist einfach die XOR-Verknüpfung Bit für Bit in meiner Zahl. Tell me more... Wie wärs mit noch mehr Beispielen zu Bitweise XOR?
z1 00110011 z2 00000000 -------- z1 XOR z2 00110011
z1 00110011 z2 11111111 -------- z1 XOR z2 11001100
Interessant! Ein XOR mit einer Reihe von Nullen bewirkt exakt gar nichts - fertigt also eine Kopie von der ursprünglichen Zahl an, ein XOR mit einer Reihe von Einsen invertiert meine Zahl. Die Anweisung ob ich meine Zahl bei der Rückumwandlung invertieren muss steckt also in diesem XOR. Ein XOR hat also die Eigenschaft ein Bit zu flippen wenn XOR 1 ausgeführt wird. Möchten wir Bit Nummer 3 von rechts invertieren, XOR-verknüpfen wir das 3. Bit einfach mit einer 1, der Rest ist 0.
z1 00110011 z2 00001000 -------- z1 XOR z2 00111011
Diesen Vorgang in C/C++ aufgeschrieben würde wie Folgt aussehen:
1 2 3 4 5 6 7 8 | uint8_t z1 = 0b00110011; // 8-Bit Zahl z1 uint8_t z2 = 0b00001000; // 8-Bit Zahl z2 // XOR-Verknuepfung von z1 und z2 in z3 speichern: uint8_t z3 = z1 ^ z2; // Bitweise-Operator fuer XOR: ^ // Alternativ: Bit-Shift! uint8_t z4 = z1 ^ (1 << 3); // 0b00000001 um 3 St. nach links |
Man kann es auch mit dem Bit-Shift-Operator (Zeile 8) schreiben: Die 1 an der 3. Stelle von rechts ist auch eine 1 an Stelle 0 um 3 nach links verschoben! Die Eigenschaft, die wir beobachten, ein Bit zu flippen bzw. umzuschalten wird auch als Bit-Toggle bezeichnet. Zum Nachdenken für Dich: Was ist eine Zahl XOR sich selbst?
Bitweise mit anderen logischen Operatoren
Mit XOR (^) haben wir nur eines von den paar Bitweise Operatoren kennengelernt. Im Tutorium dieser Woche haben wir ja gesehen, dass wir u.a. Aussagen mit einem logischen AND oder OR verknpüfen können. Und natürlich funktionieren die beiden Verknüpfungsmethoden auch bitwise, also Bit für Bit was nun hier mit dessen nützlichen Eigenschaften in der Bitmanipulation vorgestellt wird. Bitmanipulation ist übrigens was wir mit dem Bit-Toggle z.B. gemacht haben - also ich manipuliere ein einziges Bit.
Bitweise OR
Bitweise OR funktioniert so, dass eine Zahl Bit für Bit OR-verknüpft wird:
z1 00110011 z2 10001010 -------- z1 OR z2 10111011
Es ist besonders nützlich um ein Bit an einer Stelle auf 1 zu setzen. Beispiel: Wir wollen Bit Nummer 3 von rechts setzen.
z1 00000000 z2 00001000 -------- z1 = z1 OR z2 00001000
Äquivalenter Code in unserer geliebten Programmiersprache:
// 8-Bit Zahl z1 uint8_t z1 = 0b00000000; // Das 3. Bit von z1 setzen // Operator fuer OR: | z1 |= 0b00001000; // Funktioniert natuerlich auch mit Shift: z1 |= (1 << 3);
Bitweise AND
Beim Bitweise AND analog: Eine Zahl wird Bit für Bit verANDet - also 1 als Ergebnis, wenn beide Bits 1.
z1 00110011 z2 10001010 -------- z1 AND z2 00000010
Mit einem Bitweise AND kann man überprüfen, ob ein Bit 0 oder 1 ist, bzw. ein Bit auslesen. Dazu muss das Bit an der gewünschten Stelle zunächst um den Stellenwert verschoben (Bit-Shift) und anschließend AND-verknüft werden. Wir wollen mal das 4. Bit v.r. auslesen:
z1 01010101 -------- z1 = (z1 >> 4) 00000101 z2 00000001 -------- z1 = z1 AND z2 00000001 (bool) z1 1
// 8-Bit Zahl z1 uint8_t z1 = 0b01010101; // Ist Bit Nr. 4 gleich 1? // Operator fuer BW-AND: & uint8_t ergebnis = (z1 >> 4) & 1; if(ergebnis) printf("Bit 4 ist 1!"); else printf("Bit 4 ist 0!");
Zusätzlich gibt es noch den unären Bitwise NOT-Operator, der einfach wie ein XOR voller Einsen alle Bits einmal invertiert. Lese mehr zum Thema z.B. auf Wikipedia: Bit manipulation (engl.), Bitwise operations in C (engl.).
Die Bitweise Abkürzung für Hausaufgabe 11
Jetzt wo wir uns die Grundlagen erarbeitet haben, sind wir endlich gut gerüstet für die Abkürzung der 11. Hausaufgabe. Habe Euch ja bereits gesagt, dass die Zweierkomplement-Darstellung "die topaktuelle Darstellung" von vorzeichenbehaftete Zahlen ist und auch aktiv im Rechner verwendet wird. Folgt also, dass wenn wir eine Zahl als signed int, signed char, signed wasauchimmer speichern, der Compiler die Dezimalzahl vollautomatisch die richtige Bitfolge der Zahl in Zweierkomplement-Darstellung bringt*.
Alles was wir also für die Hinumwandlung schreiben müssen ist, dass wir die Zahl in 8-Bit konvertieren und dann den Vektor Bit für Bit befüllen wollen:
vector<bool> int_to_twocomplement(vector<bool> tc, int x){ for(uint8_t i = 0; i < 8; ++i) tc.push_back((bool)(((int8_t)x >> i) & 1)); return tc; }
Ungelogen. Das sind 2 Zeilen: Unsere Zahl x wird in eine signed-8-Bit Zahl überführt. Anschließend wird sie in den Vektor reingeschrieben indem wir in einer for-Schleife jedes Bit einzeln aus der Zahl auslesen -> Bitweise AND! Müssen nur noch den Vektor zurückgeben. Wird uns kein leerer Vektor übergeben, müssen wir uns natürlich noch einen Vektor bauen (+1 Zeile).
Um aus dem 2K-Vektor eine normale Zahl zu bauen müssen wir lediglich eine signed-8-Bit Zahl richtig befüllen, indem wir in ner Schleife das i-te Element an die i-te Stelle des Bits setzen!
int twocomplement_to_int(vector<bool> tc){ int8_t tcNumber = 0; for(uint8_t i = 0; i < 8; ++i) tcNumber |= ((int8_t)tc.at(i) << i); return tcNumber; }
Et voila! Disclaimer: Punktabzug für diese Lösungsansätze gibt es aber trotzdem, da ZKLENGTH variabel sein kann und diese Lösung ausschließlich für 8 Bit funktioniert. Sinn des Artikels ist es aber, Euch einen kleinen Einblick in die Welt der Bitweise Operatoren und Bitmanipulationen zu gewähren. Diese sind durchaus wichtig für einen E-Techniker, der irgendwann hardwarenah programmiert: Beispielsweise setzt man Register im Mikrocontroller durch Bitmanipulation. Habe mal willkürlich ein Datenblatt vom nem Mikrocontroller rausgesucht. Auf Seite 7 sieht man die einzelnen Bits und Bedeutungen sehr gut:
