Binäre Zahlendarstellung

Auf der Startseite haben wir uns die die vier Stellen des Wertes 1337 im dezimalen Zahlensystemen angesehen.

Nun übertragen wir 1337 mal ins Binäre Zahlensystem. Eine kurze Rechnung sagt uns, dass Tausenddreihundertsiebenunddreißig in binärer Darstellung 10100111001 ist.

1 * 2^10 = 1 * 1024 = 1024
0 * 2^ 9 = 0 *  512 =    0
1 * 2^ 8 = 1 *  256 =  256
0 * 2^ 7 = 0 *  128 =    0 
0 * 2^ 6 = 0 *   64 =    0
1 * 2^ 5 = 1 *   32 =   32
1 * 2^ 4 = 1 *   16 =   16
1 * 2^ 3 = 1 *    8 =    8
0 * 2^ 2 = 0 *    4 =    0
0 * 2^ 1 = 0 *    2 =    0
1 * 2^ 0 = 1 *    1 =    1
----------------------------
10100111001 (binär) = 1337 (dezimal)

Die binäre Zahl beginnt wie die dezimale mit der höchstwertigen Ziffer auf der linken Seite. Die 11. Stelle im Binären entspricht 2^10, also dem Wert 1024, die vierte Stelle im Dezimalen 10^3, also dem Wert 1000. Addiert man die Werte der einzelnen Stellen, erhält man den Gesamtwert der Zahl - egal in welchem Zahlensystem.

Binäre Zahlen im Computer

Im Computer sieht das ganze ähnlich aus. Die Ziffer nennt man „das Bit“ (kurz für „Binary Digit“, auf Deutsch: binäre Ziffer). Wenn das Bit auf 1 steht, sagt man „das Bit ist gesetzt“ (engl. „The bit is set“), und wenn das Bit auf 0 steht, dann sagt man „das Bit ist nicht gesetzt“ (engl. „The bit is cleared“).
Abgesehen von der Benennung gibt es bei Computern noch eine andere wichtige Besonderheit: Zahlen in Computern haben eine beschränkte Größe.
Dies hat den Grund, dass man in Computern nicht unendlich viel Platz hat um Zahlen zu speichern und weil Rechenoperationen für Variablen mit feststehenden Größen viel einfacher umzusetzen sind. 1)

Was bedeutet das für uns?

Erstens bedeutet es, dass wir ab jetzt binäre Zahlen mit allen führenden Nullen anschreiben werden, also so:

00001100 (zwölf)

um zu symbolisieren, dass die höheren Bits der Variablen zwar „da sind“, aber nicht gesetzt. 2)

Weiter bedeutet es, dass unser Wertebereich nicht mehr ins Unendliche geht. Auf dem Papier können wir immer mehr Einsen und Nullen hinzufügen und die Zahl kann beliebig groß werden und auch dementsprechend mehr Platz auf dem Papier verbrauchen (größere Darstellung). Wie bereits erwähnt hat der Computer aber nicht beliebig viel Platz auf seinem „Papier“. Deswegen sind dem Wertebereich klar definierte Grenzen auferlegt. Sagen wir, wir nehmen eine Zahl mit dem Wert Zweihundertdreiundfünfzig (dezimal 253), und haben für die Darstellung der Zahl 8 Bits Platz. Die binäre Darstellung für diese Zahl sieht so aus:

11111101

Wäre diese Zahl auf dem Papier könnten wir ohne Probleme noch 3 hinzuaddieren, und das Ergebnis würde einfach nur eine Stelle mehr bekommen:

100000000

Da wir aber davon ausgegangen sind, dass wir nur Platz für 8 Bits haben, verlieren wir das höchste Bit wieder. Das Ergebnis ist „00000000“ also schlicht und einfach Null. Wie ihr gesehen habt, wird aus einer recht hohen Zahl auf einmal eine kleine. Diesen Vorgang nennt man „Überlauf“ oder „Overflow“.

Ab wann ein Overflow auftritt hängt von der Größe der Variable ab. In unserem Beispiel waren es 8 Bits, also die höchste Zahl ist 28 -1. Wir ziehen 1 wieder ab, da wir 0 mit einbeziehen. Für 8 Bit ist das damit der dezimale Zahlenraum von 0 bis 255.

In heute gängigen PC-Systemen werden Variablengrößen meist in Bytes gemessen. Ein Byte hat (üblicherweise) 8 Bits, man spricht auch vom „Oktett“. In C ist der Datentyp „char“ mit einem Byte gleichzusetzen. Ein übliches „int“, oder ein Zeiger hat 4 Bytes, das bedeutet 32 Bits. Mit 32 Bits hat ein vorzeichenloses „int“ somit einen Wertebereich von 0 bis 4'294'967'295 (dezimal).

CPUs werden hingegen meist in Bitbreiten angeben. Moderne Computer haben in der Regel eine Registerbreite von 32 oder 64 Bit. Eine 32 Bit CPU kann damit bis maximal 4'294'967'295 zählen. Würde man eins dazu addieren, erhielte man wieder einen Überlauf und das Ergebnis ist 0.

Negative Zahlen

Auf dem Papier kann man negative Zahlen genauso darstellen, wie man Dezimalzahlen darstellt, indem wir ein Minus davorsetzen:
- 1210 = - 11002

Ein erster Versuch - das Vorzeichen

Um negative Zahlen im Computer darzustellen könnte man etwas ähnliches tun: wir stellen ein Bit der vorhandenen Zahl ab und schreiben ihm die Bedeutung des Vorzeichens zu. Wenn es gesetzt ist, soll die Zahl negativ sein und wenn es nicht gesetzt ist, dann soll die Zahl Positiv sein. In unserem Beispiel (und in heutigen Computern) werden wir das MSB 3) verwenden
Somit wäre - 2310 = 1001 0111

Wir dürfen nun nicht vergessen, dass wir nun ein Bit weniger Platz für die Darstellung des Betrages haben, also in unserem Beispiel 7. Damit hätten wir einen Wertebereich von 27 -1 = 127.

Das Problem an dieser Darstellungsart ist Folgendes: Bis jetzt wissen nur wir, was das höchste Bit bedeutet. Um dem Computern das korrekte Addieren beizubringen, müsste man zuerst das Bit abfragen und dann je nach Status des Bits zwischen Addieren oder Subtrahieren hin- und herschalten - das ist noch viel zu kompliziert, als dass es effektiv sein kann.

Der zweite Versuch - das Einser- Komplement

Um das Rechnen mit negativen Zahlen zu vereinfachen, kann man das Einser- Komplement verwenden: Soll eine Zahl negiert werden, so werden alle Bits der Zahl einfach umgedreht. Beispiel:

aus 1710 = 0001 00012 wird -1710 = 1110 11102

Reserviert man das höchste Bit für das Vorzeichen, passt das Einser- Komplement gut mit unserem oberen Versuch zusammen: ist eine Zahl positiv, ist das höchste Bit nicht gesetzt. Wird die Zahl negiert, so verändert sich auch das höchste Bit, und die Zahl ist somit negativ.

Es entstehen 2 Probleme:

  • Die Zahl 0 hat nun 2 Darstellungsmöglichkeiten: 0000 0000 (+0) und 1111 1111 (-0).
  • Die Addition ist nun immer noch nicht so einfach: man muss die beiden Zahlen addieren, und falls es bei der letzten Ziffer einen Carry (Übertrag, Rest) gibt, muss dieser an der ersten Ziffer hinzuaddiert werden. Kleines Beispiel:

17 + (-8) = 9

         0001 0001  (17) 
      +  1111 0111  (-8) 
     ------------------- 
  -->  1 0000 1000 
                +1  <--
     ------------------- 
         0000 1001 ( 9)

Die Eins, die bei der ersten Addition „übersteht“ muss hinten angehängt werden, damit man das richtige Ergebnis bekommt.

Das Einserkomplement hat bei einer Zahl von 8 Bits einen Wertebereich von -(27-1) = -127 bis +(27-1) = 127.

Der dritte Versuch - das Zweierkomplement

Eine bessere Möglichkeit negative Zahlen darzustellen bietet das sogenannte „Zweierkomplement“, das auch tatsächlich in modernen Computern verwendet wird.

Das Zweierkomplement einer Zahl wird gebildet, indem man zuerst das Einserkomplement der Zahl bildet, und dann 1 hinzuaddiert.

2710 = 000110112
-2710 = 111001002 + 1 = 111001012

Die Eigenschaften dieser Darstellung sind erstaunlicherweise sehr Vorteilhaft: Negiert man eine Zahl 2 mal, so kommt wieder die ursprüngliche Zahl heraus, genau so wie es sein müsste:

2710 * (-1) = 000110112 = 111001002 + 1 = 111001012 = -2710
-2710 * (-1) = 111001012 * (-1) = 000110102 + 1 = 2710

Die Addition von Zahlen in Zweierkomplementdarstellung funktioniert durch eine einfache Addition, und zwar ohne den Rest wieder hinzuaddieren zu müssen:

         0001 0001  (17) 
      +  1111 1000  (-8) 
     ------------------- 
  (!)  1 0000 1001  ( 9)

Das Rufzeichen soll andeuten, dass der „Carry“ ignoriert werden muss. Tut ihr das, bekommt ihr 0000 10012, was 910 entspricht, was auch das korrekte Ergebnis ist.

Der Wertebereich des Zweieromplements bei einer Zahl mit 8 Stellen geht von -27 = -128 bis 27-1 = 127.


Dies war nur eine kleine Einführung in die binäre Zahlendarstellung des Computers. Für eine etwas detailliertere Beschreibung kann ich Kapitel 2.1.1 des eBooks „PC Assembly Language“ von Dr. Paul Carter empfehlen. Es ist hier zu finden: http://www.drpaulcarter.com/pcasm/

Wers gerne etwas genauer und mathematischer hat, der möge sich diese Webseite zu Gemüte führen: http://www.cs.uaf.edu/~cs301/notes/Chapter4/node2.html Dort findet ihr dann (unter Einsatz von einigem Hirnschmalz) auch ziemlich Ausführliche Dinge über das Binärsystem.


Autorendiskussion

1) Es gibt zwar Modelle mit deren Hilfe man mit Zahlen nahezu beliebiger Größe arbeiten kann, allerdings sind diese nur in Programmbibliotheken verfügbar, die nicht für Anfänger gedacht sind.
2) Achtung: Führende Nullen im C-Quelltext werden als oktale Ziffern angesehen! 15 hat den dezimalen Wert 15, 015 hat den dezimalen Wert 13!
3) Most Significant Bit - höchstwertiges Bit