gdi002_bits_de.tex

\chapter{Bits und Bytes}
\epigraph{10 is always the base}{}
\newcommand{\short}[1]{Abk.~\texttt{#1}}
%
\section{Zahlensysteme}
\index{Zahlensysteme}
%
Eine der bekannteren Grundlagen der Informatik ist, dass in der Informatik
auch andere Zahlensysteme als das übliche Dezimalsystem zur Anwendung kommen.
Vorgänge in der Software und Hardware lassen sich in jedem beliebigen
Zahlensystem abbilden, da die Zahl als mathematisches Objekt verwendet wird
und nicht über ihre Repräsentation. Es hat sich jedoch herausgestellt, dass das
Dezimalsystem nicht für jeden Anwendungsbereich eignet ist.

\index{Radix}
Bei der Verwendung von mehreren Zahlensystemen hat es sich etabliert,
die Basis (\emph{Radix}) als Index neben die Repräsentation zu schreiben.
Die Zahl 42 in Dezimaldarstellung wäre also mit $42_{10}$ und die Zahl 4
in Binärdarstellung wäre mit $100_2$ zu notieren.
%
\subsection{Terminologie}
%
\begin{figure}[ht]
  \begin{center}
    \framebox[3\width]{4}
    \framebox[3\width]{8}
    \framebox[3\width]{6}
    \framebox[3\width]{3}
  \end{center}
  \caption{Zahlen als Sequenz von Ziffern.}
  \label{fig:seq_digits}
\end{figure}

\index{Alphabet}
Zahlensysteme sind so aufgebaut, dass eine Zahl als eine Sequenz von Ziffern
beliebiger Länge dargestellt werden kann. Die Menge der Ziffern bildet dabei
das sogenannte \emph{Alphabet}.

\subsection{Basis 10}
\label{sec:bits_numeric_systems_10}
\index{Dezimalsystem}
%
Der Grund für das Entstehen des Dezimalsystems (\short{dec}) liegt in der
Anzahl der Finger an beiden Händen eines Menschen. Bereits in der Volkschule
lernen Kinder mithilfe der Finger die arithmetischen Operationen kennen und
setzen sich dabei mit dem Dezimalsystem auseinander. Durch Wörter wie ,,zehn``
haben wir uns auch eigene Wörter geschaffen, die Zahlen in ihrer dezimalen
Repräsentation bezeichnen.%
%\footnote{Lojban spricht Zahlen so aus wie einzelnen Ziffern von links nach rechts
% angeordnet sind. Diese Konvention wird auch gerne bei der Aussprache von Zahlen
% in einem Zahlensystem verwendet, die für die verwendete Sprache unüblich sind.
% $100_2$ wäre nach dieser Konvention ,,eins-null-null``.}
\footnote{Für die Aussprache einer Zahl in einem anderen Zahlensystem als dem
üblichen Dezimalsystem gilt als Konvention, dass sie gleich der Aussprache der
einzelnen Ziffern ist. So wird $100_2$ etwa als ,,eins-null-null`` ausgesprochen.}

Das Dezimalsystem umfasst 10 verschiedene Ziffern.
\begin{align*}
         \text{Alphabet}_{\text{dec}} &= \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \\
  \card{\text{Alphabet}_{\text{dec}}} &= 10 
\end{align*}

%\aside % TODO
\index{Indexing}
Fraglich ist, welche die erste natürliche Zahl ist. Einerseits wird mit $1$ zum
Zählen begonnen und andererseits ist $0$ die Ziffer mit dem niedrigsten Wert.
Jedenfalls hat es sich seit der C-Programmiersprache in der überwiegenden
Mehrheit der Programmiersprachen durchgesetzt \emph{Indexing} (das
Referenzieren eines Eintrags in einer Sequenz) mit Null beginnend durchzuführen
(,,null-basierte Nummerierung``).%
\footnote{Ausnahmen (chronologisch betrachtet nach C) bilden etwa die Sprachen
Lua, Mathematica, MATLAB und SQL}
% http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
% TODO: EWD831
%
\subsection{Basis 2}
\index{Binärsystem}
%
Das Zahlensystem mit der Basis 2 wird als Binärsystem (\short{bin}) bezeichnet.
Binärzahlen  haben ihre starke Verbreitung durch die einfache technische
Realisierung in der Elektronik erlangt. ,,Strom ein`` und ,,Strom aus``
sind zwei Zustände, die im Binärsystem abgebildet werden können.
Die überwiegende Mehrheit der heutigen Maschinen
implementiert binäre Operationen.
%
\subsection{Basis 16 und 8}
\index{Hexadezimalsystem}
%
Das Hexadezimalsystem (\short{hex}) setzt 16 als Radix voraus. Das Besondere an
16 ist der Zusammenhang zum Binärsystem ($2^4 = 16$). Selbiges gilt für
das Oktalsystem (\short{oct}, Basis 8), welches die Zahlen 0 bis 7 verwendet:
%
\begin{align*}
  \text{Alphabet}_{\text{hex}} &= \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F\} \\
  \card{\text{Alphabet}_{\text{hex}}} &= 16 
\end{align*}
%
\begin{align*}
  \text{Alphabet}_{\text{oct}} &= \{0, 1, 2, 3, 4, 5, 6, 7\} \\
  \card{\text{Alphabet}_{\text{oct}}} &= 8
\end{align*}
%
\subsection{Stellenwertsystem}
%
\index{Übertrag}
Die vorgestellte Definition, dass eine ,,Zahl eine Sequenz von Ziffern`` ist,
basiert auf unserer Auffassung, dass Zahlen in einem Stellenwertsystem
dargestellt werden. Beim Zählen reservieren wir eine \emph{Stelle} und
positionieren der Reihe nach die Ziffern mit ansteigendem Wert.
Hat die Stelle den höchsten Wert des Alphabets erreicht,
kommt es zum \emph{Übertrag}. Dabei wird die nächste Stelle inkrementiert
und die vorigen Stellen auf den niedrigsten Wert gesetzt.
Mit diesem Konzept von Ersetzen \& Übertragen
können wir uns eine abzählbar unendliche Struktur bilden.
%
\begin{figure}[ht]
  \begin{displaymath}
    007 \xrightarrow{\text{Ersetzen}} 008 \xrightarrow{\text{Ersetzen}}
    009 \xrightarrow{\text{Übertrag}} 010 \xrightarrow{\text{Ersetzen}}
    011
  \end{displaymath}

  \caption{Inkrementieren mit natürlichen Dezimalzahlen.}
\end{figure}

Die Dezimalzahlen seien in einer sequentiellen Datenstruktur gespeichert.
Indexing innerhalb dieser Struktur $n$ mit dem Index $i$ erfolgt mit der Notation
$n[i]$. Mit $n = 100_2 = \set{1, 0, 0}$ referenziert $n[0]$ die $1$ und
$n[2]$ die erste $0$. Eine Zahl $z$ lässt sich dann wie folgt als eine Summe
darstellen:
\[
  z = \sum_{i=0}^d n[i] \cdot 10^i
\]

Die Zahl $10$ muss in der Formel entsprechend dem Radix für andere
Zahlensysteme angepasst werden. Die Zahl aus Abbildung~\ref{fig:seq_digits}
kann somit auf folgende Weise aufgelöst werden.
\[
  4\cdot10^3 + 8\cdot10^2 + 6\cdot10^1 + 3\cdot10^0
\] \[
  4000 + 800 + 60 + 3
\] \[
  4863
\]

\subsection{Das Bit}
\index{Bit}
%
Ein Bit (Abk. \emph{BInary digiT}) bezeichnet eine Stelle in einem
binären Zahlensystem. In einem Bit können zwei Zustände unterschieden werden.
%
\begin{table}[ht]
  \begin{center}
    \begin{tabular}{cc}
     \hline
      Stellen (d) & mögliche Zustände (s) \\
     \hline \hline
           1      &       2    \\
           2      &       4    \\
           3      &       8    \\
           4      &      16    \\
           5      &      32    \\
           6      &      64    \\
           7      &     128    \\
           8      &     256    \\
     \hline
    \end{tabular}
    \caption{Entwicklung der Stellen im Vergleich zur Anzahl der Zustände.}
    \label{tab:digits_states}
  \end{center}
\end{table}
%
Die Anzahl der möglichen Zustände wächst logarithmisch zur Basis 2
(\emph{logarithmus dualis}); wie in Tabelle~\ref{tab:digits_states}
dargestellt. Der Zusammenhang zwischen der Anzahl der abbildbaren
Zustände $s$ und der Anzahl der Ziffern $d$ erklärt sich durch
$s = 2^d$ bzw. logarithmisch mit $\log_2{s} = d$.

\index{Byte}
Folgende Konvention hat sich etabliert:
Eine Menge von 8 Bits wird als ein \emph{Byte} bezeichnet.
Ein Byte ist meist die kleinste Speichergröße, die
von einer CPU in einem modernen Rechner angesprochen werden kann.
Bekannt ist das Byte aus Einheiten wie Megabyte und Gigabyte, um
die Speichergröße von Medien wie Caches, Festplatten und USB-Sticks
anzugeben. In Tabelle~\ref{tab:si_units} wird die Umrechnung der
Speichergrößen in Bytes dargestellt.
%
\begin{table}[ht]
  \begin{center}
     \begin{tabular}{cc}
      \hline
       Einheit                 & Bytes \\
      \hline \hline
       1~KB (\emph{Kilobyte})  & 1000~Bytes \\
       1~MB (\emph{Megabyte})  & $10^6$~Bytes \\
       1~GB (\emph{Gigabyte})  & $10^9$~Bytes \\
       1~TB (\emph{Terabyte})  & $10^{12}$~Bytes \\
      \hline
     \end{tabular}
     \caption{Einheiten mit SI-Präfixen.}
     \label{tab:si_units}
  \end{center}
\end{table}

Leider sind Begriffe wie ,,Kilobyte`` in der Praxis nicht so eindeutig definiert, wie es wünschenswert wäre. Ein Kilo ($2^{10}$) weicht bei dieser Definition von Tabelle~\ref{tab:si_units} um 24 Werte vom üblichen Kilo ($10^3$) ab. Es gab mehrere Versuche die Präfixe auf das Binärsystem anzupassen, allerdings spiegelt die genannten Tabelle die übliche Konvention wider.\footnote{Zur Unterscheidung wurde von der IEC der Präfix Kibi/Mebi/Gibi für die Basis 2 eingeführt.}

\subsection{Overflows und Underflows}
%
\index{Overflow}
Wir sprachen bei einer Zahl immer vom mathematischen Objekt Zahl. Dieses
besitzt jedoch eine wichtige Einschränkung nicht: Länge. Unendliche Länge
lässt sich nicht in der echten Welt realisieren und beschränkt uns in
unserer Verwendung von Zahlen.

Daher müssen wir Zahlen auf eine Länge beschränken. Die Zahlen liegen
dann an einem beliebigen Ort im Speicher. Eine Ganzzahl (engl.~,,Integer``)
wird üblicherweise in einer Größe von 32bit%
\footnote{Wie wir jetzt wissen, sind das 4 Bytes. Diese können 4294967296
(ca. 4.3 Milliarden) verschiedene Zustände annehmen.}
gespeichert.

\begin{figure}[ht]
  \begin{center}
    \framebox[3\width]{1} \framebox[3\width]{1} \framebox[3\width]{0} \framebox[3\width]{1} $+ 1 =$ \\
    \framebox[3\width]{1} \framebox[3\width]{1} \framebox[3\width]{1} \framebox[3\width]{0} $+ 1 =$ \\
    \framebox[3\width]{1} \framebox[3\width]{1} \framebox[3\width]{1} \framebox[3\width]{1} $+ 1 =$ \\
    \framebox[3\width]{0} \framebox[3\width]{0} \framebox[3\width]{0} \framebox[3\width]{0} \hspace{27.5pt}~
  \end{center}
  \caption{Illustration eines Overflow in der letzten Zeile.}
  \label{fig:overflow}
\end{figure}
%
Aufgrund der beschränkten Länge tritt das Problem des Overflows bzw.
Underflows auf. Ein Integer bestehend aus nur 4 Bits, kann 16 ($2^4 = 16$)
Zustände annehmen. Der zugehörige Wertebereich reicht von $0$ bis $15$.
Wird nun dieser Wert inkrementiert, kommt es zum Übertrag, wobei keine
neue Stelle zur Verfügung steht. In Folge dessen geht der neue Wert der
zusätzlichen Stelle verloren. Die restlichen Stellen werden entsprechend
dem Übertrag auf die niedrigste Zahl zurückgesetzt. Statt $16$ erhalten wir
$0$ (siehe Abbildung~\ref{fig:overflow}).

\index{Underflow}
Der Underflow beschreibt das Äquivalent für das Dekrementieren.
Der Over- und Underflow kann durch Techniken wie Ganzzahlarithmetik vermieden
werden, doch aufgrund des Geschwindigkeitsverlustes und der Komplexität
verzichtet man in maschinennahen Umgebungen darauf. Dynamische Programmiersprachen
(etwa Python und ruby) bieten oft Ganzzahlen mit unendlicher Genauigkeit
an\footnote{Nur beschränkt durch die Größe des Hauptspeichers.} und verstecken
die Umsetzung auf maschinennahe Zahlen mit beschränkter Länge.
%
\section{Konvertierung zwischen Zahlensystemen}
\index{Konvertierung!zwischen Zahlensystemen}
%
Liegt eine Repräsentation einer Zahl vor, so lässt sie sich in ein beliebiges
anderes Zahlensystem mit Stellenwertordnung umrechnen, indem man eines der
hier vorgestellten Verfahren verwendet.
%
\subsubsection{Moduloansatz über die Basis 10}
%
Die einfachste Variante besteht darin die Zahl pro Stelle aufzulösen,
sie in unsere Basis 10 zu bringen und dann wieder entsprechend der Potenzen
aufzubauen.

\[ 42_{16} \]
%
Wir spalten die Zahl in ihre Potenzdarstellung\footnote{%
auch ,,Wissenschaftliche Schreibweise`` genannt} auf:
\[ 4\cdot 16_{10}^1 + 2\cdot 16_{10}^0 \]
%
Wir rechnen diese Zahl aus:
\[ 64_{10} + 2_{10} = 66_{10} \]
%
Wir legen für $66_{10}$ eine Zahl $8^0$ ($=1$) an und rechnen mit der Basis 10 weiter.
Der Faktor ist das Ergebnis der Operation $\frac{(66)}{8^0}\mod{8^1}$.
Bei uns also $2$.
\[ 66 = \ldots + 2\cdot 8^0 \]
%
Wir legen $8^1$ ($=8$) an. Das Ergebnis der Operation
$\frac{(66-2\cdot8^0)}{8^1}\mod{8^1}$ ist $0$.
\[ 66 = \ldots + 0\cdot 8^1 + 2\cdot 8^0 \]
%
Wir legen $8^2$ ($=64$) an. Das Ergebnis der Operation
$\frac{(66-2\cdot8^0-0\cdot8^1)}{8^2}\mod{8^2}$ ist $1$.
\[ 66 = 1\cdot8^2 + 0\cdot8^2 + 2\cdot8^0 \]
%
Da $66-2\cdot8^0-0\cdot8^1-0\cdot8^2 = 0$ sind wir am Ziel angekommen:
\[ 102_{8} \]

\subsubsection{Der Kettenansatz}
%
Zahlen lassen sich als verschachtelte Kette darstellen.
Wir spalten dabei immer einen Restwert in einer alternierenden
Sequenz von Addition und Multiplikation ab.
%
\[
  59_{10}
\] \[
  (58 + 1)
\] \[
  ((29)\cdot2 + 1)
\] \[
  (((14)\cdot2 + 1)\cdot2 + 1)
\] \[
  ((((7)\cdot2 + 0)\cdot2 + 1)\cdot2 + 1)
\] \[
  (((((3)\cdot2 + 1)\cdot2 + 0)\cdot2 + 1)\cdot2 + 1)
\] \[
  ((((((1\cdot2 + 1)\cdot2 + 1)\cdot2 + 0)\cdot2 + 1)\cdot2 + 1)
\] \[
  \Rightarrow 111011_2
\]

\subsubsection{Der Tabellenansatz}
%
Der Tabellenansatz erlaubt einen einfachen Umgang und stellt die explizite
Frage ,,Brauche ich diesen Wert, um meinen Zielwert zu erreichen?{}``. Erfolgt
die Antwort mit ,,Ja``, wird eine 1 notiert; sonst 0. Das Funktionsprinzip
wird in Tabelle~\ref{tab:table_approach} dargestellt. Wir konvertieren die
Zahl $59_{10}$ ins Binärsystem. Dazu tragen wir auf einer Linie die
2er-Potenzen absteigend auf (die höchste Potenz muss die größte Potenz sein,
die kleiner-gleich der gesuchten Zahl ist). Wir bearbeiten die Zahlen
von links nach rechts. Wir fragen uns, ob die Zahl $32$ kleiner oder gleich
$59$ ist (d.h. ob sie ,,gebraucht`` wird). Wenn ja, tragen wir darunter
eine 1 ein. Wenn nein, tragen wir darunter eine 0 ein.
Wir fragen uns, ob die Zahl $32+16$ kleiner $59$ ist. Ja, daher 1.
$32+16+8$ ist auch kleiner $59$ und daher tragen wir eine 1 ein.
$32+16+8+4$ wäre jedoch $60$ und überschreitet unseren Wert $59$.
Wir lehnen diese 2er-Potenz mit einer $0$ ab. Mit $32+16+8+2+1$ erreicht
die Summe genau unsere Zahl $59$; in binär $111011_2$.
%
\begin{table}[ht]
  \begin{center}
    \begin{tabular}{lccccccccc}
     \hline
      59 & & & 32 & 16 & 8 & 4 & 2 & 1 \\
     \hline \hline
         & & &  1 &  1 & 1 & 0 & 1 & 1
    \end{tabular}
    \caption{Tabellenansatz.}
    \label{tab:table_approach}
  \end{center}
\end{table}

\subsubsection{Stellenweise Methode}
%
Es sei $d$ der Zielradix und $s$ der Ausgangsradix. Ist $s > d$ und
ist $s$ ein Vielfaches von $d$ können wir die Zahl pro Stelle konvertieren.
Dabei wird eine Stelle durch $\frac{\log{s}}{\log{d}}$ Stellen ersetzt.

Wir beschreiben die Bedingung informal: Erreicht man den Zielradix durch
Potenzieren des Ausgangsradix
(etwa $2^n = 16$ mit $n=4$ oder $3^n = 9$ mit $n=2$), können wir jede
Ziffer der Ausgangszahl verwenden und mit $n$ Stellen in die Zielbasis
bringen und schlussendlich die Einzelzahlen aneinander fügen
(\emph{konkatenieren}).

Als Beispiel betrachten wir in \ref{tab:positional_approach} die
Konvertierung von FACE$_{16}$ ins Binärsystem. So wird etwa $F$
mit $n=4$ binär durch $1110$ dargestellt.
%
\begin{table}[ht]
  \begin{center}
    \begin{tabular}{cccc}
     \hline
      \multicolumn{4}{c}{0xFACE} \\
     \hline
      F & A & C & E \\
     \hline
      1111 & 1010 & 1100 & 1110 \\
     \hline
    \end{tabular}
    \caption{Stellenweise Methode.}
    \label{tab:positional_approach}
  \end{center}
\end{table}

\section{Arithmetische Operationen}
%
Moderne Rechenmaschinen nutzen ALUs (,,arithmetic logical unit``),
um Rechenoperationen mit Bytes durchzuführen. Diese umfassen etwa:
%
\begin{itemize}
 \item Addition
 \item Subtraktion
 \item Multiplikation
 \item Division
\end{itemize}

Die arithmetischen Operationen lassen sich mit den bekannten
Methoden in allen Zahlensystemen rechnen und werden daher hier
nicht näher erörtert. Es sei nur erwähnt, dass es auf einer
Maschine zu Fehlerfällen kommen kann wie etwa eine Division
durch Null.

\section{Bitweise Operationen}
%
Eine ALU kann auch Operationen durchführen, die auf die einzelnen Bits
angewandt werden:
%
\begin{itemize}
 \item Und-Verknüpfung
 \item Oder-Verknüpfung
 \item Negation
 \item Exklusive Oder-Verknüpfung
\end{itemize}
%
Die Operationen werden im Kapitel~\ref{sec:propositional_logic}
behandelt.

Beachte, dass Bits genau die beiden aussagenlogischen Ausdrücke
\textsl{wahr} und \textsl{falsch} repräsentieren können, jedoch diese
Werte praktisch nie auf modernen Maschinen durch wirkliche Bits
gespeichert werden, da (wie erwähnt) die kleinste adressierbare
Speichereinheit ein Byte ist.