View
218
Download
2
Category
Preview:
Citation preview
Prof. Dr. Nikolaus Wulff
Einführung in die Informatik I
Das Rechnen in Zahlensystemen zur Basis b=2, 8, 10 und 16
2© Prof. Dr. Nikolaus Wulff Informatik I
Zahlensysteme
• Neben dem üblichen dezimalen Zahlensystem zur Basis 10 sind in der Informatik Systeme zur Basis 2, 8 und 16 gebräuchlich.
• Zahlen werden gebildet aus den einzelnen Ziffern (Symbolen) eines Alphabets ∑.
• Die Anzahl |∑| der Elemente des Alphabets entspricht der jeweiligen Basis b.
• Die mit Hilfe dieser Symbole bildbaren Wörter w ∈∑*
werden mit dem Stellenwertverfahren des Zahlen-systems auf die natürlichen Zahlen abgebildet.
• Dasselbe Symbol a∈∑ hat verschiedene Bedeutung.
ℕ
3© Prof. Dr. Nikolaus Wulff Informatik I
• Zahlen sind Wörter (an-1
an-2
...a0)
b ∈ ∑* gebildet aus
den b verschiedenen Zeichen des Alphabets ∑.
• Zur Schreibweise gehört eine Interpretation innerhalb eines Stellenwertsystems zur Basis b:
Zahlendarstellung
an−1 an−2a1 a0b=∑ j=0
n−1a j b
j und 0≤a jb
– Achtung: – Das Symbol ∑ wird auf der Folie in zwei Bedeutungen verwendet:
1) Der griechischer Buchstabe ∑ (Sigma) als Abkürzung für das Alphabet, bzw. ∑* zur Kennzeichnung aller Wörter des Alphabets.
2) Als mathematisches Zeichen für die Summation.
Darstellung einer vorzeichenlosen Ganzzahl zur Basis b
4© Prof. Dr. Nikolaus Wulff Informatik I
Dezimalsystem• Basis b=10
Benutze Symbole/Ziffern ∑ = {0,1,2,3,4,5,6,7,8,9}
• Interpretation:
• Beispiel:
– (1011)10
= 1103 + 0102 + 1101 + 1100
• = 11000 + 0100 + 110 + 11 = „eintausendelf“
an−1 an−2a1 a010=∑ j=0
n−1a j 10 j
5© Prof. Dr. Nikolaus Wulff Informatik I
Binärsystem• Basis b=2
Benutze Symbole/Ziffern ∑ = {0,1}
• Interpretation:
• Beispiel:
– (1011)2 = 123 + 022 + 121 + 120 = 8 + 2 + 1= „elf“
an−1 an−2a1 a02=∑ j=0
n−1a j 2
j
6© Prof. Dr. Nikolaus Wulff Informatik I
Hexadezimalsystem• Basis b=16
Symbole ∑ = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
• Interpretation:
• Beispiel:
– (1011)16
= 1163 + 0162 + 1161 + 1160
• = 1 4096 + 0256 + 116 + 11
• = „viertausendeinhundertdreizehn“
an−1 an−2a1 a016=∑ j=0
n−1a j 16 j
7© Prof. Dr. Nikolaus Wulff Informatik I
Oktalsystem• Basis b=8
Symbole ∑ = {0,1,2,3,4,5,6,7}
• Interpretation:
• Beispiel:
– (1011)8 = 183 + 082 + 181 + 180
• = 1512 + 064 + 18 + 11
• = „fünfhunderteinundzwanzig“
an−1 an−2a1 a08=∑ j=0
n−1a j 8
j
8© Prof. Dr. Nikolaus Wulff Informatik I
Rechnen im Stellenwertsystem
• Die Addition erfolgt ähnlich zum gewohnten Schulrechnen zur Basis 10:
• Der „Überlauf“ passiert nicht bei der Zehn sondern der jeweilige Basis b:
3423+ 5678
9101
1 1 1
01012
+ 00112
10002
1 1 1
34238
+ 56768
113218
1 1 1 1
346416
+ D6D616
10B3A16
1 1
9© Prof. Dr. Nikolaus Wulff Informatik I
Basiswechsel
• Offensichtlich sind neben der Basis 2, 8, 10 und 16 beliebig viele verschiedene Zahlensysteme möglich.
• Zahlen dürfen nicht einfach blind miteinander ver-glichen oder verarbeitet werden, wenn sie in unter-schiedlichen Basen repräsentiert werden.
• Es ist daher wichtig geeignete Vorschriften zur Umrechnung von einer Basis p zur Basis q zu haben.
• Eine solche eindeutige Rechenvorschrift wird auch Algorithmus genannt.
• Algorithmen können von Hand – oder besser noch vom Computer – abgearbeitet/ausgeführt werden.
10© Prof. Dr. Nikolaus Wulff Informatik I
Basiswechsel bei b=2k
• Soll zwischen den Basen 2, 8, 16 umgerechnet werden, so bietet die Darstellung b=2k ein einfaches Verfahren mit Hilfe der Gruppierung nach 3 und 4 Bitfeldern an:
•
•
• 3 Bit bilden eine Oktalzahl
•
• Ein Nibbel bildet eine Hexzahl
...0101101101012
010 110 110 101(2 6 6 5 )
8
0101 1011 0101
(5 B 5 )16
5B516
= 146110
= 26658 = 0000010110110101
2
146110
=
11© Prof. Dr. Nikolaus Wulff Informatik I
Modulo-Division
• Dividiert man eine natürliche Zahl durch eine andere natürliche Zahl so ergibt sich ein Quotient q und ein Rest r.
• Diese Art der Modulo-Division mit Rest wird in der Informatik mit mod bezeichnet, um sie von der gewöhnlichen Division div zu unterscheiden.
• Die Menge wird bei der Division nicht verlassen. Es gilt z. B. 9 div 3 = 3 jedoch 7 div 3 = 2, da 2.333... keine natürliche Zahl ist. ( )
• Es gilt die Beziehung: z = (z div d)*d + (z mod d)
z∈ℕd≠0
ℕ
2. 333∈ℚ⊂ℝ≠ℕ
z=q×d r ⇒ z /d=q Rest r
12© Prof. Dr. Nikolaus Wulff Informatik I
Hornerschema
• Basiswechsel lassen sich effizient bestimmen mit der Darstellung nach dem Hornerschema zur Basis b:
–
–
• Obige Zahl z geteilt durch b ergibt•
•
• weitere Division von mit b ergibt •
•
• d.h. jede weitere Division liefert eine weitere Ziffer der Darstellung zur Basis b, bis der Quotient Null ist.
z
z=∑ j=0
n−1a j b
j=an−1 ban−2ba2ba1ba0
an−1 ban−2ba2b≡z
a1 Rest a0
an−1 ban−2bba2 Rest a1
13© Prof. Dr. Nikolaus Wulff Informatik I
Divisionsalgorithmus
1. Teile die Zahl z durch die Basis b und ermittele den Quotienten q und den Rest r.
2. Ist der Quotient q≠0 setze z=q und fahre fort mit 1.
3. Die einzelnen Reste rk von rückwärts gelesen sind
die Repräsentation von z= (rnr
n-1...r
0)
b in der Basis b.
436110:8=545 + Rest 1
54510:8= 68 + Rest 1
6810:8= 8 + Rest 4
810:8= 1 + Rest 0
110:8= 0 + Rest 1
436110:16=272 + Rest 9
27210:16= 17 + Rest 0
1710:16= 1 + Rest 1
110:16= 0 + Rest 1
436110
= 104118 = 1109
16
14© Prof. Dr. Nikolaus Wulff Informatik I
Umrechnung von b=10 nach b=2k
• Zur Umrechnung einer Zahl z im Zehnersystem zur Basis 2 empfiehlt es sich diese zunächst in das Oktalsystem zu überführen (8 liegt dicht an 10) und dann jedes Oktalsymbol als 3-Bitzahl zu schreiben:
z = 436110
= 104118 siehe vorhergehende Folie
1 0 4 1 1 8
001 000 100 001 001
z = 00010001000010012
in 16 Bit Darstellung
15© Prof. Dr. Nikolaus Wulff Informatik I
Vorzeichenbehaftete Ganzzahlen
• Bis lang wurden nur natürliche Zahlen betrach-tet, um auch negative Zahlen darzustellen wird das höchste Bit v als Vorzeichenbit interpretiert:
• Da ein Bit für das Vorzeichen verwendet wird gibt es – bei gleicher Bitlänge –, nur noch halb so viele positive Zahlen, im Vergleich zur Repräsentation ohne Vorzeichen.
z∈ℕz∈ℤ
(v an−2 an−3…a1 a0)2
Darstellung einer Ganzzahl zur Basis 2
16© Prof. Dr. Nikolaus Wulff Informatik I
Zweierkomplement
• Die Darstellung negativer Zahlen sind allerdings nicht im Stellenwertsystem codiert!
• Die naive Verallgemeinerung der Codierung ist falsch:
• Es gäbe zwar gleich viele positive wie negative möglich darstellbare Zahlen, hätte aber zur Folge, dass es eine positive und eine negative Null gibt.
• Es wird daher eine unsymmetrische Codierung gewählt, das Zweierkomplement, es entsteht durch Invertierung aller Bit und Addition von Eins.
(v an−2 an−3…a1 a0)2≠(−1)v∑ j=0
n−2a j 2
j
17© Prof. Dr. Nikolaus Wulff Informatik I
Darstellung im Zweierkomplement
0000000100100011010001010110011110001001101010111100110111101111
Bitfolge unsigned
0123456789
101112131415
01234567
-0-1-2-3-4-5-6-7
01234567
-1-2-3-4-5-6-7-8
01234567
-8-7-6-5-4-3-2-1
mögliche Interpretationen
positiv
negativ
01234567
-7-6-5-4-3-2-1-0
18© Prof. Dr. Nikolaus Wulff Informatik I
Invertierung einer Binärzahl
• Eine Binärzahl wird invertiert, indem alle Nullen durch Einsen und alle Einsen durch Nullen ersetzt werden.
• Diese Invertierungsoperation lässt sich einfach in der Hardware einer CPU realisieren.
x=∑ j=0
n−1a j2
j⇒ x=∑ j=0
n−11−a j2
j
x=0100⇒ x=1011x=0101⇒ x=1010
x=0000⇒ x=1111
19© Prof. Dr. Nikolaus Wulff Informatik I
Negative Binärzahlen• Der Vorteil der Zweierkomplementdarstellung ist die
einfache Berechenbarkeit durch Invertierung der Bitfolge und anschließende Addition von 1.
–
–
–
• Die Subtraktion zweier Zahlen lässt sich somit im Binärsystem auf einfache Addition zurückführen.
x=0100⇒ x=1011
x1=1100≡−x
x− y = x− y= x y1= x y 1
−x=x1
20© Prof. Dr. Nikolaus Wulff Informatik I
Beispiel: Binäre Subtraktion
4−6=4−6=461
610=01102 ⇒ 610=10012 −610=10102
410=01002
01002
+ 10012
11012
+
12
1110
2
11102=−210=410−610
Rechnung: 01002
+ 10102
11102
oder
Ergebnis:
21© Prof. Dr. Nikolaus Wulff Informatik I
Gleitkommazahlen
• Mit Hilfe der Zweierkomplementdarstellung ist es möglich negative und positive Ganzzahlen darzustellen. Gebrochene oder irrationale Zahlen lassen sich jedoch so nicht darstellen.
• Insbesondere gehen bei der Division zweier Ganzzahlen die Nachkommastellen verloren!
– Gleitkommaarithmetik: 19/10 = 1.9
– ganzahlige Arithmetik: 19/10 = 1.(9) = 1• 19/10 liefert 1 Rest 9 und die 9 wird nicht berücksichtigt!
• Um den Zahlenbereich von auf auszudehnen sind Nachkommastellen erforderlich.
ℤ ℝ
x∈ℤ
22© Prof. Dr. Nikolaus Wulff Informatik I
Idee der Gleitkommazahlen
• Darstellung von Gleitkommazahlen im Zehnersystem:–
•
•
• Die Kommastelle lässt sich „Durchschieben“:
• 34.567 lässt sich zur Basis 10 darstellen als die Ganzzahl 34567 mit dem negativen Exponenten -3 oder als 0.34567 mit Exponent 2 („Normalform“).
34.567=3.4567×101=0.34567×102
=34567×10−3
(Vorzeichen, Exponent, Mantisse)
v e a−1a−m10=−1v 10e∑ j=1
ma j 10− j
v an−1a0 , a−1a−m10=−1v∑ j=−m
n−1a j 10 j
34.567=3⋅1014⋅100
5⋅10−16⋅10−2
7⋅10−3
23© Prof. Dr. Nikolaus Wulff Informatik I
• Gleitpunkzahlen werden zur Basis 2 dargestellt als:•
•
• Gleitpunktzahlen werden als 4-Byte (einfache) oder 8-Byte Zahlen (doppelte Genauigkeit) codiert.
• Format nach Standard IEEE 754-1985:
Gleitpunktzahlen
...(Vorzeichen, Exponent, Mantisse)
4 Byte: 1-Bit, 8-Bit, 23-Bit
8 Byte: 1-Bit, 11-Bit, 52-Bit
-127 ≤ e ≤ 128
-1023 ≤ e ≤ 1024
(v e a−1…a−m)2=(−1)v 2e∑ j=1
ma j 2
− j
10-38 ≤ f ≤ 1038
10-308 ≤ d ≤ 10308
Bereich
Beim Exponent ebias
wird fest als bias 127 bzw. 1024 zu e hinzugerechnet, so dass
ebias
intern als vorzeichenlose Ganzzahl verarbeitet wird und es gibt ein Hidden Bit.
24© Prof. Dr. Nikolaus Wulff Informatik I
Prinzip der Gleitpunktzahl
3.62510=3100.62510=⋯0001120.62510
0.62510=0.1012
• Die Koeffizienten aj ergeben sich ähnlich den
Ganzzahlen mit sukzessiver Multiplikation mit 2j
• Durchschieben des Binärpunkts
Probe: 2-1 +2-3 =0.625
3.62510=⋯00011.1012
0 0 ...0 0 0 0 0 1 0 0 0 1 1 1 0 1
3.62510=⋯00011.1012=0.111012×22
0.62510 ×2 = 1.2510
0.2510 ×2 = 0.510
0.510 ×2 = 1.010
Achtung:Dies ist
nicht das IEEE Format!
25© Prof. Dr. Nikolaus Wulff Informatik I
IEEE754-Gleitpunktzahl
• Im IEEE Format wird das erste signifikante Bit der Mantisse eingespart, um einen Faktor 2 im mög-lichen Zahlenbereich zu gewinnen das Hidden Bit.
• Die erste 1 der Mantisse vor dem Komma wird nicht abgespeichert und der Exponent um den Bias 127 verschoben (=> vorzeichenloser Exponent):
0 1 ...0 0 0 0 0 0 0 0 0 0 1 1 0 1
3.62510=⋯00011.1012=1.11012×21
3.62510=⋯00011.1012=+1.11012×21
21=2(128−127) 12810=100000002
IEEE754
26© Prof. Dr. Nikolaus Wulff Informatik I
Darstellungsfehler
• Nicht alle Zahlen lassen sich exakt zu beliebiger Basis b darstellen und es kommt daher zu Fehlern.
1/3 = 0.13 ≃0.3333⋯310≃0.0101010101⋯012
2 /3 = 0.23 ≃0.6666⋯610≃0.1010101010⋯102
1/10 = 0.110≃0.00011⋯00112
1/5 = 0.210≃0.0011⋯00112
0.110≃0.000110012=0.0976562510
Probe: Fehler 2.3 10-3 8-Bit 1.4 10-4 12-Bit
∞
∞
∞
∞
∞
∞
0.110≃0.000110011001 2=0.09985...10
0.110≃0.0001100110011001 2=0.0999908...10
Achtung 3-Bit gehören in den Exponenten
27© Prof. Dr. Nikolaus Wulff Informatik I
Fehlerabschätzung• Mit der Darstellung
–
•
•
• lässt sich der Quantisierungsfehler abschätzen zu:–
–
–
• Für e=0 ergibt sich für m=8, 12 und 16 die Abschätzung |
x | ≤ 410-3, 210-4 und 110-5 und
für m=23 und 52 |x| ≤ 110-7 und 210-16.
x= x̃+δx
x=−1v 2e∑ j=1
∞
a j 2− j
δx=(−1)v 2e∑ j=m+1
∞
a j 2− j
∣δx∣=2e∑ j=m+1
∞
a j 2− j ≤ 2e∑ j=m+1
∞
2− j = 2e−m
x=−1v 2e∑ j=1
ma j 2
− j∑ j=m1
∞
a j 2− j
28© Prof. Dr. Nikolaus Wulff Informatik I
Zusammenfassung
• Darstellung natürliche Zahlen zu beliebiger Basis b.
• Übliche Zahlensysteme sind Binär-, Oktal- und Hexadezimal- sowie die bekannten Dezimalzahlen.
• Negative Zahlen erfordern ein Vorzeichenbit und werden durch die Zweikomplementdarstellung repräsentiert.
• Gleitpunktzahlen werden zur Basis 2 dargestellt mit Angabe von Vorzeichen, Exponent und Mantisse.
• Nicht alle Gleitpunktzahlen lassen sich zur Basis 2 exakt genau darstellen.
– Z.B. alle Zahlen 1/p mit p Primzahl>2.
Recommended