4.3 Binärdarstellung natürlicher Zahlen
Zahlen im Computer speichern
Bisher haben wir Zahlendarstellungen umgerechnet. Jetzt geht es darum, wie Zahlen im Computer gespeichert werden. Dafür steht eine feste Anzahl \(n\) von Bits zur Verfügung. Sie erlaubt genau \(2^n\) verschiedene Bitmuster. Welche Zahl ein Muster bedeutet, legt die gewählte Codierung fest.
Hier betrachten wir natürliche Zahlen einschließlich \(0\). Für sie ist die Binärdarstellung die naheliegende Codierung: Jede Binärziffer belegt ein Bit. Hat die Darstellung weniger als \(n\) Ziffern, werden links Nullen ergänzt. Für Zahlen mit mehr als \(n\) Binärziffern reichen die Bits nicht aus.
Definition 4.2 (Vorzeichenlose Binärdarstellung). Ein Bitmuster \(x_{n-1}\ldots x_1x_0\) mit \(x_j\in\{0,1\}\) stellt den Wert
\[ x=\sum_{j=0}^{n-1}x_j2^j \]
dar. \(x_{n-1}\) heißt Most Significant Bit (MSB), \(x_0\) heißt Least Significant Bit (LSB).
Aus den Gewichten des kleinsten und des größten Bitmusters ergibt sich der darstellbare Zahlenbereich.
Mit \(n\ge1\) Bits lassen sich vorzeichenlos genau die Zahlen
\[ 0,1,\ldots,2^n-1 \]
darstellen.
Das kleinste Muster ist \(00\ldots0\), das größte ist \(11\ldots1\) mit
\[ \sum_{j=0}^{n-1}2^j=2^n-1. \]
Ein Byte besteht aus acht Bits. Es kann vorzeichenlos die Zahlen von \(0\) bis \(2^8-1=255\) darstellen.
Beispiel: Den Rotanteil eines Pixels lesen
Bei RGB-Bildern wird häufig jeder der drei Farbanteile Rot, Grün und Blau in einem eigenen Byte gespeichert. Der Wert \(0\) bedeutet keinen Anteil dieser Farbe, \(255\) den größten darstellbaren Anteil.
Der Rotanteil eines Pixels ist als Byte 11001010 gespeichert. Welchen Wert hat dieser Farbkanal?
Eine feste Wortbreite macht sichtbar, welche Stellengewichte zu den einzelnen Bits gehören.
Beispiel. Die Zahl \(101\) besitzt als 8-Bit-Wert die Darstellung
\[ (101)_{10}=(01100101)_2. \]
\[ \begin{array}{c|cccccccc} \text{Bitposition}&7&6&5&4&3&2&1&0\\ \hline \text{Bit}&0&1&1&0&0&1&0&1\\ \text{Gewicht}&128&64&32&16&8&4&2&1 \end{array} \]
Das MSB ist \(0\), das LSB ist \(1\). Die führende Null gehört zur festen Wortbreite, ändert den Zahlenwert aber nicht.
Addition natürlicher Zahlen
Die Summe zweier natürlicher Zahlen ist wieder eine natürliche Zahl. Auch ihre Binärdarstellungen lassen sich stellenweise addieren. Bei einer festen Bitzahl muss das Ergebnis jedoch in den darstellbaren Bereich passen.
Beispiel: Addition ohne Überlauf
Binäre Addition folgt denselben Stellenregeln wie Dezimaladdition. Dabei gilt \(1+1=(10)_2\): Wir schreiben \(0\) und übertragen \(1\) in die nächste Stelle.
\[ \begin{array}{r} \phantom{+}00101101\\ +00110111\\ \hline 01100100 \end{array} \]
Also ist \((45)_{10}+(55)_{10}=(100)_{10}\). Die Summe liegt im mit acht Bits darstellbaren Bereich von \(0\) bis \(255\).
Bei einer festen Wortbreite kann eine Summe mehr Stellen benötigen, als gespeichert werden können. Das zeigt die größte 8-Bit-Zahl.
Beispiel: Überlauf bei acht Bits
Die natürliche Zahl \(255\) lässt sich mit acht Bits als 11111111 darstellen. Bei der Addition von \(1\) entsteht
\[ \begin{array}{r} \phantom{+}11111111\\ +00000001\\ \hline 1\,00000000 \end{array} \]
Mathematisch gilt \(255+1=256\). Dafür sind neun Bits nötig. Wenn nur acht Bits gespeichert werden, bleibt 00000000 übrig: Der Übertrag links vom MSB geht verloren. Das ist ein Überlauf.
Zusammenfassung
- Ein vorzeichenloses \(n\)-Bit-Wort codiert Werte von \(0\) bis \(2^n-1\).
- MSB und LSB bezeichnen die höchst- und niedrigstwertige Stelle.
- Binäre Addition verwendet Überträge wie die Dezimaladdition.
- Bei fester Wortbreite kann ein zusätzlicher Übertrag einen Überlauf verursachen.