Binary Code

Binärdarstellung von Zahlen

Im Computer werden Dezimalzahlen in der Binärdarstellung verarbeitet. Die Zahl +1 ist z.B. als 32 Bit Binärzahl

00000000000000000000000000000001

Negative Binärdarstellung

Um negative Zahlen darzustellen gibt es verschiedene Variante. Die einfachste ist vermutlich die Vorzeichen-Betrag-Darstellung, hier wird das erste Bit benutzt um das Vorzeichen anzuzeigen, ansonsten werden negative und positve Zahlen gleich dargestellt. Eine sehr praktische Negative Binärdarstellung ist das Zweierkomplement. Möchte man eine negative Zahl darstellen, nimmt man zuerst die Darstellung der positiven Zahlen, invertiert alle Stellen und addiert dann +1 dazu. Beispiel -1:

00000000000000000000000000000001  (== +1)
11111111111111111111111111111110  (inv)
11111111111111111111111111111111  (+ 1)

Negative Zahlen erkennt man also an der führenden 1. Das ist die größte und die kleinste darstellbare Zahle im Zweierkomplement in 32 Bit:

01111111111111111111111111111111 (+2147483647)
10000000000000000000000000000001 (-2147483647)
10000000000000000000000000000000 (-2147483648)

Wie man sieht gibt es in dieser Darstellung eine negative Zahl mehr als postive Zahlen, die kein darstellbares Gegenstück mehr hat.

Shift

Mit einem Shift kann man Binärzahlen nach rechts oder links "schieben", sie also mit 2 Multiplizieren oder teilen.

00011010  =26
00110100  =52  (<<1)
00011010  =26  (>>1)

Oft kann man in einer Operation maximal um eine fünfstellige Binärzahl shiften. Größere Shifts muss man in mehreren Zügen durchführen.

<< 11111
>> 11111

Logischer Arithmetischer Shift

arithmetic vs logical shift Wenn man eine negative Zahl mit einem arithmetischen Shift nach rechts schiebt, werden die Stellen links mit dem bisherigen führenden Zeichen aufgefüllt, das Vorzeichen bleibt also gleich

10000000000000000000000000010110  =-2147483626
11000000000000000000000000001011  =-1073741813 >> 1)

Bei einem logischen Shift nach rechts werden die führenden Stellen dagegen immer mit 0 aufgefüllt, bei negativen Zahlen ändert sich also das Vorzeichen

10000000000000000000000000010110  =-2147483626
01000000000000000000000000001011  = 1073741835 (>>> 1)  
 

Gleitkommazahlen als Binärzahlen

Die Norm IEEE 754 definiert eine Standarddarstellungen für binäre Gleitkommazahlen in Computern. Beispiel, wir wollen die Zahl +18,4 als Single 32 Bit Gleitkommazahl darstellen.

Beispiel +18,4 als Single darstellen. Wir haben 32 Bit zur Verfügung. So werden die 32 Bit benutzt:

1234567891011121314151617181920212223242526272829303132
SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM

Das erste Bit (S) ist sehr einfach bestimmt, es ist das Vorzeichen der Zahl, + ist 0, - ist 1. In unserem Beispiel also 0. Für den Rest müssen wir ein paar kleine Schritt durchlaufen. Als erstes konvertieren wir den Teil vor der Kommastelle (18) in Binärdarstellung

2^42^32^22^12^0
168421
10010
18==16+2

Wir erhalten also

das merken wir uns kurz.

Dann konvertieren wir den Teil nach dem Komma (0,4) in eine Binärdarstellung. Statt 2^n benutzen wir jetzt 1/(2^n)=2^(-n). Als erstes erhalten wir so 0.5, das ist größer als 0.4, also nehmen wir davon 0 Stück. Dann erhalten wir 0.25, das ist kleiner als 0.4 also nehmen 1 Stück davon und erhalten als Rest 0.4-0.25=0.15 Als nächstes vergleichen wir den Rest 0.15 gegen 0.125 usw.

n1234567891011
1/(2^n)0,50,250,1250,06250,031250,0156250,00781250,003906250,0019531250,000976563...
0110011001...
todo0,40,150,0250,0250,0250,0093750,00156250,00156250,00156250,000585938...

Wir erhalten also

011001100110011...

Mit der bereits vorher berechneten Darstellung von 18:

18,4= 10010,011001100110011...

Jetzt schieben wir das Komma so weit nach links (durch Multiplikation mit 2) bis vor dem Komma nur noch genau eine 1 steht

18,4= 1,0010011001100110011... * 2^4

Da vor dem Komma nach diesem Verfahren immer eine 1 steht (es gibt in der Binärdarstellung ja nur 0 oder 1), braucht man die nicht zu speichern:

0010011001100110011... * 2^4

Damit haben wir jetzt die letzten 23 Bits, die Mantisse (MMMM..) der Single Zahl ermittelt.

00100110011001100110110

Jetzt fehlt noch der Exponent (EEEE...). Der Exponent war 4. Wir haben 8 Stellen, um den Exponent zu speichern. Der größte Exponent, der mit 7 Stellen darstelle wäre (Bias) ist die

01111111=(2^7)-1=127

Wir addieren unseren Exponenten auf diesen und schieben damit den Exponenten in die positiven Zahlen, das macht es leichter zwei Gleitkommazahlen zu vergleichen.

127+4=131=10000011

Damit ergibt sich folgende Binärdarstellung der Gleitkommazahl:

0 10000011 00100110011001100110110

Die Umkehrung läuft analog:

  • Erstes Zeichen ist das Vorzeichen
  • Vom Exponenten 127 abziehen
  • Die Mantisse um 1, ergänzen

Spezielle Werte: Exponent und Mantisse 0, die Zahl 0 oder eine sehr kleine Zahl Exponent 0, Mantisse >0: Denormalisierte Zahl. Hier wird nicht mehr implizit 1, angenommen. Damit lassen sich sehr kleine Zahlen (mit verminderter Genauigkeit und möglicherweise langsamer Rechengeschwindigkeit) darstellen. Exponent mit 1en gefüllt, Mantisse 0: +/- Unendlich Exponent mit 1en gefüllt, Mantisse>0 NAN

Gleitkommazahlen Links

Mad Irish: Converting a Decimal Digit to IEEE 754 Binary Floating Point