Kap1 - Zahlendarstellung und Datentypen PDF

Sommersemester 2024 Automaten und Rechnerarchitekturen Kapitel 1: Zahlendarstellung und elementare Datentypen (Wiederholung) Prof. Dr. Uwe Brinkschulte apl. Prof. Dr. Mathias Pacher Inhalt Zahlendarstellung Elementare Datentypen Zahlensysteme Darstellung negativ...

Sommersemester 2024 Automaten und Rechnerarchitekturen Kapitel 1: Zahlendarstellung und elementare Datentypen (Wiederholung) Prof. Dr. Uwe Brinkschulte apl. Prof. Dr. Mathias Pacher Inhalt Zahlendarstellung Elementare Datentypen Zahlensysteme Darstellung negativer Zahlen Gleitkommazahlen Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 1 Zahlendarstellung Menschen arbeiten mit verschiedensten Zahlen. Für den Rechner sind diese effizient zu kodieren. Zum einen sollte Speicherplatz gespart werden. Zum anderen sollte möglichst mit diesen Zahlen eine hohe Rechenleistung erbracht werden. Beides führt zu einer Vielzahl von möglichen Kodierungen. Mit bestimmten kann der Rechner direkt umgehen. Dies sind die Maschinen-Datentypen. Andere sind durch Software zu behandeln. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 2 Systeme zur Informationsdarstellung  Systeme zur Informationsdarstellung unterscheiden sich im wesentlichen durch die Anzahl der Zustände, welche die kleinstmögliche Informations-Einheit annehmen kann  Anzahl der Zustände = Wertigkeit oder Entscheidungsgrad des Systems  Beispiel: Die kleinste Informationseinheit (Stelle) unseres Zahlensystems kann 10 verschiedene Zustände annehmen => es besitzt die Wertigkeit 10  Systeme der Wertigkeit 10 heißen Denärsysteme  Die kleinstmögliche Wertigkeit eines solchen Systems ist 2  Systeme der Wertigkeit 2 heißen Binärsysteme Wertigkeit 2 ist technisch am leichtesten zu realisieren => Im Rechner benutztes System Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 3 Maschinen-Datentypen Ein Datentyp wird durch eine Wertemenge und Operationen auf den Werten beschrieben. Bei Maschinen-Datentypen sind die Operationen als Maschinenbefehle implementiert. Typische Datentypen sind z.B.: Bit: Wertemenge: 0,1 Operationen: AND, OR, XOR, NOT, Vergleich,... Byte/Character: Wertemenge: Bitmuster (8 Bit) z.B. 00101101 Operationen: Identitätsvergleich, Shift, bitweises XOR,... Integer: Wertemenge: Ganze Zahlen (endliche Menge (z.B. 16 Bit)) Operationen: ADD, SUB, MUL, DIV, Vergleich,... Gleitkommazahlen: Wertemenge: Gleitkommazahlen (Vorzeichen, Mantisse und Exponent:) Operationen: ADD, SUB, MUL, DIV Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 4  Binärsysteme N-stellige Binärwerte Einzelne Stellen heißen Bits Byte: Ein Byte: 8 Bit. Z.B. : 01001101 (MSB, Most Significant Bit) (LSB, Least Significant Bit) Character -> Byte: kodierte Darstellung alphanumerischer Zeichen z.B. nach dem ASCII-Zeichensatz Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 5 ASCII-Codierung 000 001 010 011 100 101 110 111 0000 NUL DLE SPACE 0 @ P ' p 0001 SOH DC1 ! 1 A Q a q 0010 STX DC2 " 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB ´ 7 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K [ k { 1100 FF FS , < L \ l | 1101 CR GS - = M ] m } 1110 SO RS. > N ^ n ¯ 1111 SI US / ? O _ o DEL Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 6 Zahlensysteme Zur Darstellung von Zahlen mit einem b-wertigen System muß nun den einzelnen Stellen ein Wert zugeordnet werden Stellenwertsysteme Zahlendarstellung in Form einer Reihe von Ziffern z, wobei der Dezimalpunkt rechts von z0 plaziert sei: znzn-1...... z1z0. z-1z-2… z-m Jeder Position i der Ziffernreihe ist ein Stellenwert zugeordnet, der eine Potenz der Wertigkeit bi des Zahlensystems ist. b heißt auch Basis des Zahlensystems Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 7 Zahlensysteme Der Wert Xb der Zahl ergibt sich dann als Summe der Werte aller Einzelstellen zb: n X b = zn bn+ zn-1 bn-1+ … + z1 b1 + z0+ z-1 b-1+ …+ z-mb-m = zb i  m i i Das denäre System mit dieser Stellenwertfunktion heißt Dezimalsystem Das binäre System mit dieser Stellenwertfunktion heißt Dualsystem Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 8 Zahlensysteme Interessante Zahlensysteme: Dualzahlen, Oktalzahlen, Dezimalzahlen, Hexadezimalzahlen Ganze Zahlen (Integer) im Rechner: N-stellige Binärzahl (meist im Dualsystem) mit häufig 8, 16, 32 oder 64 Bits mit Vorzeichen (signed) oder ohne Vorzeichen (unsigned) Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 9 Hexadezimalkodierung Dual Dezimal Hex Kurze Darstellung einer 4-Bit-Integerzahl 0000 0 0 0001 1 1 0010 2 2 2 Hexadezimalkodes können effizient ein 0011 3 3 Byte darstellen 0100 4 4 Beispiel: 7D = 01111101 = 7*16+13 = 125 0101 5 5 0110 6 6 Hexadezimalzahlen werden häufig durch 0111 7 7 ein vorgestelltes 0x dargestellt, z.B. 0x7D. 1000 8 8 1001 9 9 1010 10 A 1011 11 B 1100 12 C 1101 13 D 1110 14 E 1111 15 F Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 10 Umwandlung von Zahlensystemen Umwandlung einer Zahl beliebiger Basis b in eine Dezimalzahl nach der Stellenwertformel: Xb= znbn+ zn-1bn-1+ … + z1b1 + z0+ z-1b-1+ … + z-mb-m Umwandlung einer Dezimalzahl in eine Zahl beliebiger Basis b: Euklidischer Algorithmus Horner-Schema Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 11 Umwandlung von Zahlensystemen Euklidischer Algorithmus: Z = zn10n+ zn-110n-1+ … + z1101 + z0 + z-110-1+ … + z-m10-m = ypbp + yp-1bp-1 + … + y1b1 + y0+ y-1b-1 + … + y-qb-q Ziffern werden sukzessive, beginnend mit der höchstwertigsten Ziffer, berechnet: 1. Schritt: Berechne p gemäß der Ungleichung bp  Z < bp+1 2. Schritt: Ermittle yi und den Rest R durch Division von Z durch bi yi = Z div bi; R = Z mod bi; yi ε {0, 1, … , b-1} 3. Schritt: Wiederhole 2. Schritt für i = p, p-1, … , ersetze dabei nach jedem Schritt Z durch R, bis R= 0 oder bis bi (und damit der Umrechnungsfehler) gering genug ist. Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 12 Umwandlung von Zahlensystemen Beispiel: Umwandlung von 15741,23310 ins Hexadezimalsystem Schritt : 163  15741,233 < 164 => höchste Potenz 163 Schritt : 15741,233 : 163 = 3 Rest 3453,233 Schritt : 3453,233 : 162 = D Rest 125,233 Schritt : 125,233 : 16 = 7 Rest 13,233 Schritt : 13,233 : 1 =D Rest 0,233 Schritt : 0,233 : 16-1 = 3 Rest 0,0455 Schritt : 0,0455 : 16-2 = B Rest 0,00253 Schritt : 0,00253 : 16-3 = A Rest 0,000088593 Schritt : 0,000088593 : 16-4 = 5 Rest 0,000012299 (=> Fehler) => 15741,23310  3D7D,3BA516 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 13 Umwandlung von Zahlensystemen Horner-Schema Getrennte Betrachtung des ganzzahligen und des gebrochenen Anteils a. Umwandlung des ganzzahligen Anteils n Schreibe ganze Zahl Xb=  yib i i 0 durch fortgesetztes Ausklammern in der Form Xb= ((…(((ynb + yn-1) b + yn-2) b + yn-3) b … ) b + y1) b + y0 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 14 Umwandlung von Zahlensystemen Verfahren: Die gegebene Dezimalzahl wird sukzessive durch die Basis b dividiert Die jeweiligen ganzzahligen Reste ergeben die Ziffern der Zahl Xb in der Reihenfolge von der niedrigstwertigen zur höchstwertigen Stelle Beispiel: Wandle 1574110ins Hexadezimalsystem 1574110: 16 = 983 Rest 13 (D) 98310: 16 = 61 Rest 7 (7) 6110: 16 = 3 Rest 13 (D) 310: 16 = 0 Rest 3 (3) => 1574110 = 3D7D16 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 15  Umwandlung von Zahlensystemen Umwandlung des Nachkommateils gebrochener Zahlen: 1 Auch der gebrochene Anteil  yb i  m i i einer Zahl lässt sich entsprechend schreiben: Yb= ((…((y-mb-1+ y-m+1) b-1+ y-m+2) b-1+ … + y-2) b-1+ y-1) b-1 Verfahren: Sukzessive Multiplikation des Nachkommateils der Dezimalzahl mit der Basis b des Zielsystems Die jeweiligen ganzzahligen Anteile ergeben nacheinander die y-i in der Reihenfolge der höchstwertigsten zur niederwertigsten Nachkommaziffer Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 16 Umwandlung von Zahlensystemen Beispiel: Umwandlung von 0,23310 ins Hexadezimalsystem 0,233 * 16 = 3, 728 } z -1 = 3 0,728 * 16 = 11, 648 } z-2 = B 0,648 * 16 = 10, 368 z -3 = A 0,368 * 16 = 5, 888 z -4 = 5 Abbruch bei genügend hoher Genauigkeit => 0,23310  0,3BA516 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 17 Komplementdarstellung Für negative Zahlen werden Komplementdarstellungen gewählt. Sie ermöglichen eine einfache Implementierung der Subtraktion und Addition mit negativen Zahlen. Es gilt für N-stellige Binärzahlen: a - b = a - b + 2N = a + 1 + 2N - 1 - b  1er-Komplement Darstellung der Zahl - b als 2N -1 –b durch einfaches Invertieren jeder Stelle (aus jeder 0 wird eine 1 und aus jeder 1 eine 0) Die Subtraktion kann durch die Berechnung von a + 1er(b) +1 erfolgen  2er-Komplement Darstellung der Zahl - b als 2N –b durch einfaches Invertieren jeder Stelle und anschließendes Addieren von 1 Die Subtraktion kann durch die Berechnung von a+2er(b) erfolgen Konsistentes rechnen mit dieser Darstellung ist auch für negative Zahlen möglich.  Darstellung in C, C++... Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 18 Gleitkommazahlen In digitalen Computern wird Arithmetik mit endlicher Genauigkeit vollzogen. Die endliche Genauigkeit impliziert, dass Zahlen, die die darstellbare Genauigkeit überschreiten, gerundet werden müssen. Bei der Gleitkommadarstellung wird eine Zahl Z so gespeichert, dass das Komma immer zur ersten von 0 verschiedenen Zahl gleitet. Dies erreicht man durch Abspalten einer entsprechenden Potenz: Da die Basis b bekannt ist, kann die Zahl durch die Mantisse m und den Exponenten e, mit jeweils fester Stellenanzahl, dargestellt werden. Die Anpassung der Gleitkomma-Zahl an diese Darstellungsform wird normalisieren genannt. Beispiel: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 19 IEEE-754 Das Institute of Electrical and Electronics Engineers (IEEE) hat einen Standard für Gleitkomma-Zahlen entwickelt, der heutzutage in fast allen Computern Verwendung findet. Gleitkomma-Zahlen werden durch ein Vorzeichen-Bit, einen Exponenten und eine Mantisse, jeweils mit fester Stellenanzahl und zur Basis 2, dargestellt. 1 0 s: Vorzeichen e: Exponent s e m m: Mantisse Im Standard IEEE-754 werden Gleitkomma-Zahlen mit verschiedenen Wertebereichen und Genauigkeiten definiert: Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 20 IEEE-754 – single Eine 32-Bit Gleitkomma-Zahl besteht aus einem Vorzeichen-Bit, einem 8-Bit Exponenten und einer 23-Bit Mantisse. 31 30 29 28 27 26 25 24 23 22 21 1 0 s e m Exponent: Der 8-Bit Exponent e kann Werte aus dem Wertebereich 0, …, 255 darstellen. Durch Subtraktion des konstanten Wertes 127 wird eine Links- und Rechtsgleitung des Kommas im Wertebereich - 127, …, 128 ermöglicht. Mantisse: Die 23-Bit Mantisse m stellt einen 24-Bit-Wert (zzgl. Vorzeichen- Bit) dar, indem das Komma über die erste von 0 verschiedene Stelle hinaus gleitet (1,m)  Normalisierung Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 21 IEEE-754 – single Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 22 Beispiele -- IEEE-754 – single Wie stellt man z.B. 3,8125 in der IEEE-754 Darstellung dar? Vorzeichenbit ist 0, da positiv Vorkommateil 3 ist binär dargestellt 11 Nachkommateil 0,8125 ist 2-1 + 2-2 + 2-4, also binär → 1101 Zusammensetzen des Vor- und Nachkommateils: 11,1101 Verschieben des Kommas hinter die erste 1 von links: 1,11101 → Exponent ist 1, da um 1 Stelle verschoben. Aufaddieren von 127 auf Exponent (= 128) und binär darstellen als 8-Bit-Wert: 10000000 Auffüllen oder kürzen der Mantisse auf insgesamt 23 Bit, wobei die 1 vor dem Komma nicht codiert wird: 11101000000000000000000 Zusammenfügen von 3,8125 als IEEE-754 - single: (Vorzeichen - Exponent - Mantisse) → 0-10000000-11101000000000000000000000 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 23 Beispiele -- IEEE-754 – single Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 24 Gleitkommaarithmetik Gegeben: Zur Vereinfachung sei Addition Subtraktion Multiplikation Division Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 25 Vergleich Zahlenbereiche bei 32 Bit Speichergröße Zweierkomplement Konstanter Abstand, Schrittweite 1 Overflow 0 Overflow 2 2 1 Gleitkommazahl Variabler Abstand Overflow 1,17549435 · 10 Overflow 0 Underflow Underflow 3,40282347 · 10 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 26 Beispiel Fahrzeug Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 27 Speicheraufbau Wortbreiten 8 Bit = 1 Byte 1 1 0 0 0 1 0 1 16 Bit = 2 Byte 1110010111000101 32 Bit = 4 Byte A C 0 1 E 5 C 5 64 Bit = 8 Byte 0A 67 D6 F7 AC 01 E5 C5 Speicheraufbau Adresse 0 0 1 2 3 Adresszählung immer Byte- 4 4 5 weise, auch wenn 64-Bit-Wörter abgelegt werden. 8 C 10 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 28 Speicheraufbau II Adresse Anordnung im Speicher 0 aligned 4 misaligned 8 je nach Wortgröße C 10 Adresse Byte-Reihenfolge 0 Big-Endian 4 MSB 2 1 LSB Little-Endian 8 C LSB 1 2 MSB 10 Brinkschulte, Pacher: Automaten und Rechnerarchitekturen 29