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:

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.

Denn diese sind im Gegensatz zu abstrakten Klassen und dynamischen Casts tatsächlich relevant für einen E-Techniker, der irgendwann hardwarenah programmiert: Beispielsweise setzt man Register im Mikrocontroller durch Bitmanipulation. Man findet es nämlich dort, wo Speicher stark begrenzt und wertvoll ist. Statt bspw. für jeden Zustand (0 oder 1) ein volles 8-Bit Int zu nehmen, ist jedes einzelne Bit von 8 Bit stellvertretend für einen Zustand, eine Information. Habe mal willkürlich ein Datenblatt vom nem Mikrocontroller rausgesucht. Auf Seite 7 sieht man die einzelnen Bits und Bedeutungen sehr gut:

http://ww1.microchip.com/downloads/en/DeviceDoc/2535S.pdf

Frank F. Zheng

10119

Hi there, it's Frank from THE VFD COLLECTIVE.

I'm a 20 year old electrical engineer student currently living in Berlin, Germany. This page, THE VFD COLLECTIVE was brought into life to promote my VFD tube digital clock (Project OpenVFD) and let everyone who enjoy doing creative nerd stuff with VFD displays and tubes to share their work.

In my free time, I'm in love with traveling, photography, hiking in the mountains, vegan food and great coffee. At home, you'll either find me learning for college or making music. Playing the piano, guitar and singing is so much fun.

Peace :)