Technische Informatik
Zahlendarstellung

• Das von uns im Alltag verwendete Dezimalsystem kennt 10 Zahlensymbole:
  $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
• Dabei ist die absolute Position der Zeichen wichtig, um den Zahlenwert zu ermitteln
• Beispiel: $123 \ne 321$
• Beispiel: $5124 = 5 \cdot 1000 + 1 \cdot 100 + 2 \cdot 10 + 4$
• Der Zahlenwert $w$ berechnet sich also wie folgt aus den Ziffern $z_{n-1}, \dots, z_1, z_0$ einer Dezimalzahl:
  
  $\begin{aligned}w &= z_{n-1} \cdot 1\underbrace{0\dots0}_{n-1} + \dots z_2 \cdot 100 + z_1 \cdot 10 + \ z_0 \cdot 1 =\\ &=\sum\limits_{i=0}^{n-1} z_i \cdot 10^i\end{aligned}$
• Bei dem Dezimalsystem handelt es sich um ein so genanntes Stellenwertsystem
• Das Dezimalsystem ist ein Stellenwertsystem mit der Basis 10

• Der Basis $b=2$ mit einem Alphabet von zwei Zahlensymbolen, $0$ und $1$, kommt in der Informatik eine besondere Bedeutung zu, da sich zwei Symbole leicht elektrisch kodieren lassen:
  • "kein Strom fließt" entspricht typischerweise der $0$
  • "Strom fließt" der $1$
  • Jede Stelle einer Binärzahl wird als "Bit" ("Binary Digit") bezeichnet
  • 1 Bit ist demnach die kleinste Informationsmenge, die gespeichert werden kann
  • 8 Bits werden als 1 Byte bezeichnet
• Die Bitfolge $(01001101)_2$ entspricht der Dezimalzahl $(77)_{10}$
  
  $\begin{align}&(01001101)_2 \\ &= 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4+ 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\\ &=0 \cdot 128 + 1 \cdot 64 + 0 \cdot32 + 0 \cdot 16+ 1 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\\ &=64 + 8 + 4 + 1\\ &=77 \end{align}$

• Eine rationale Zahl $w \in \mathbb{Q}$ kann ebenfalls in der b-adischen Darstellung angegeben werden.
• Dazu wird der Nachkommaanteil durch negative Exponenten repräsentiert
• Beispiel aus dem uns vertrauten Dezimalsystem:
  
  $913,64 = 9 \cdot 10^2 + 1 \cdot 10^1 + 3 \cdot 10^0 + 6 \cdot 10^{-1} + 4 \cdot 10^{-2}$
• Dies lässt sich wieder verallgemeinern:
  $\begin{align} w &= (z_{n-1}\dots z_2 z_1 z_0, z_{-1} \dots z_{-m})_b\\ &= \sum\limits_{i=-m}^{n-1} z_i \cdot b^i \end{align}$
  wobei $n$ die Anzahl der Vorkommastellen
  und $m$ die Anzahl der Nachkommastellen angibt
• Beispiel im Binärsystem:
  
  $\begin{align}(11,101)_2 &= 1 \cdot 2^1 + 1 \cdot 2^0 + 1 \cdot 2^{-1} + 0 \cdot 2^{-2} + 1 \cdot 2^{-3} \\ &= 2 + 1 + 0.5 + 0,125 = (3,625)_{10}\end{align}$

• Für viele Zehnerpotenzen gibt es standardisierte Präfixe, die vor den eigentlichen physikalischen Einheiten stehen, z.B. 1000 m = 1 km

• Wenn in der Informatik von 1 kByte (Kilobyte) gesprochen wird, bezeichnet dies leider nicht immer 1000 Bytes, sondern häufig 1024 Bytes. Dies führt zu Verwirrungen. Daher sollten für die Potenzen von 1024 besser die folgenden Präfixe laut IEC verwendet werden:

• Zur Entwicklung eines Algorithmus zum Umrechnen zwischen Zahlensystemen betrachten wir was passiert, wenn wir die hergeleitete Formel zur b-adischen Darstellung durch die Basis $b$ dividieren:
  $\begin{aligned}w = \sum\limits_{i=0}^{n-1} z_i \cdot b^i\Leftrightarrow \frac{w}{b} &= \frac{1}{b}\sum\limits_{i=0}^{n-1} z_i \cdot b^i\\ &= \underbrace{\left(\sum\limits_{i=0}^{n-2} z_{i+1} \cdot b^i\right)}_{s_1} + \frac{z_0}{b} \end{aligned}$
• Der erste Summand $s_1$ ist das ganzzahlige Ergebnis der Division und $z_0$ der Rest der Division
• Damit wurde gezeigt, dass die letzte Ziffer $z_0$ aus dem Rest der Division mit der gewünschten Basis $b$ errechnet werden kann
• Das ganzzahlige Ergebnis der Division stellt den Zahlenwert der verbleibenden Ziffern (ohne $z_0$) dar. Durch rekursive Anwendung können alle Ziffern bestimmt werden

• Beispiel: Umrechnung der Dezimalzahl 6485 ins Binärsystem:

6485 / 2 = 3242  Rest 1
3242 / 2 = 1621  Rest 0
1621 / 2 =  810  Rest 1
 810 / 2 =  405  Rest 0
 405 / 2 =  202  Rest 1
 202 / 2 =  101  Rest 0
 101 / 2 =   50  Rest 1
  50 / 2 =   25  Rest 0
  25 / 2 =   12  Rest 1
  12 / 2 =    6  Rest 0
   6 / 2 =    3  Rest 0
   3 / 2 =    1  Rest 1
   1 / 2 =    0  Rest 1

• Das Verfahren endet, wenn das Ergebnis der Division gleich Null ist
• Die Binärzahl kann anhand der Reste von unten nach oben ablesen werden: $(1100101010101)_2$
• Hinweis: Soll ein solcher Algorithmus implementiert werden, kann der Divisionsrest mittels der Modulo-Operation ermittelt werden: 6485 mod 2 = 1

• Beispiel: Umrechnung von $(360)_7$ ins Quinärsystem (Basis 5)
• Zunächst muss $(360)_7$ ins Dezimalsystem gewandelt werden:
  
  $(360)_7 = 3 \cdot 49 + 6 \cdot 7 + 0 \cdot 1 = (189)_{10}$
• Dann erfolgt die Umrechnung von $(189)_{10}$ ins Quinärsystem:

189 / 5 =  37  Rest 4
 37 / 5 =   7  Rest 2
  7 / 5 =   1  Rest 2
  1 / 5 =   0  Rest 1

• Die Ergebnis kann wieder anhand der Reste ablesen werden: $(1224)_{5}$
• Anstatt den Umweg über das Dezimalsystem zu gehen, hätten wir theoretisch das Verfahren auch direkt im 7er-System anwenden können. Dann müssten wir jedoch die Operationen (Division und Bildung des Rests) im 7-er System ausführen, was wir als Menschen nicht gewohnt sind.

• Zur Umwandlung von rationalen Zahlen betrachten wir den Vorkommaanteil und Nachkommaanteil getrennt:
  $\begin{align} w &= (z_{n-1}\dots z_2 z_1 z_0, z_{-1} \dots z_{-m})_b\\ &= \sum\limits_{i=-m}^{n-1} z_i \cdot b^i \\ &= \left(\sum\limits_{i=0}^{n-1} z_i \cdot b^i\right) + \left(\sum\limits_{i=-m}^{-1} z_i \cdot b^i\right)\end{align}$
• Die Umrechnung für den Vorkommaanteil ist bekannt, daher betrachten wir nun nur noch den Nachkommaanteil $\tilde{w}$:
  $\begin{align} \tilde{w} &= (0, z_{-1} \dots z_{-m})_b = \left(\sum\limits_{i=-m}^{-1} z_i \cdot b^i\right)\end{align}$

• Im Gegensatz zum Vorgehen bei der Umwandlung des Vorkommaanteils (Rest der Division) muss beim Nachkommaanteil mit der Basis $b$ multipliziert werden:
  $\begin{aligned}\tilde{w}= \sum\limits_{i=-m}^{-1} z_i \cdot b^i \Leftrightarrow \tilde{w} \cdot b &= b \sum\limits_{i=-m}^{-1} z_i \cdot b^i\\ &= \left(\sum\limits_{i=-m}^{-2} z_{i} \cdot b^{i+1}\right) + z_{-1} \end{aligned}$
• Der Summand $z_{-1}$ ist der einzige Anteil der $\ge 1$ sein kann. Damit ist der Vorkommaanteil von $\tilde{w} \cdot b$ gleich $z_{-1}$
• Der Nachkommaanteil von von $\tilde{w} \cdot b$ stellt den Zahlenwert der verbleibenden Ziffern (ohne $z_{-1}$) dar. Durch rekursive Anwendung können alle Ziffern bestimmt werden.