InfTech Tutorium 13 Zusatzmaterial
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:
(2) XOR mit VZB, VZB addiert:
Für Die Positive Zahl gilt:
(1) Schritte Rückwärts:
(2) XOR mit VZB, VZB addiert:
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?
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.
Diesen Vorgang in C/C++ aufgeschrieben würde wie Folgt aussehen:
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:
Es ist besonders nützlich um ein Bit an einer Stelle auf 1 zu setzen. Beispiel: Wir wollen Bit Nummer 3 von rechts setzen.
Äquivalenter Code in unserer geliebten Programmiersprache:
Bitweise AND
Beim Bitweise AND analog: Eine Zahl wird Bit für Bit verANDet - also 1 als Ergebnis, wenn beide Bits 1.
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:
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:
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!
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: