Polyadische Zahlensysteme (Basis- oder Stellenwertsysteme)


Inhalt dieser Seite

  1. Einführung
  2. Rechenregeln
    2.1   Grundrechenarten
    1. Dezimalsystem
    2. Binärsystem
    2.2   Komplementdarstellung
    1. Dezimalsystem
    2. Binärsystem
  3. Quellen
    Weitere Navigation

1. Einführung

Anmerkung: In der folgenden Darstellung wird konsequent zwischen den Begriffen Ziffer und Zahl unterschieden. Eine Ziffer ist ein einzelnes Element (Schriftzeichen, Symbol) in einer Zahl, die im Allgemeinen aus mehreren Ziffern besteht. Entsprechend ist ein Buchstabe ein Element (Schriftzeichen, Symbol) in einem Wort, das aus mehreren Buchstaben besteht. Kleine Zahlen können aus nur einer Ziffer bestehen. In diesem Fall bezeichnet der Begriff Zahl deren Wert und der Begriff Ziffer das Element dieser Zahl. In der Umgangssprache wird bedauerlicherweise nicht immer zwischen Ziffern und Zahlen unterschieden, sondern diese Begriffe gehen mitunter willkürlich durcheinander.

In einem polyadischen Zahlensystem (Stellenwertsystem) mit einer beliebigen Basis B hat jede Ziffer einer Zahl einen bestimmten Stellenwert, der von rechts nach links um wachsende Potenzen der Basis B zunimmt. Bei einer n-stelligen natürlichen Zahl N (einschließlich 0) beginnt das rechts mit B 0 = 1 und endet links mit B n–1. Bei einer gebrochenen (reellen) Zahl R schließen sich nach rechts m Stellen des Bruchteils an, die vom ganzzahligen Teil durch ein Komma abgetrennt werden, im englischen Sprachraum durch einen Punkt (point). Negative Zahlen haben zusätzlich ein vorangestelltes Minuszeichen, das hier zunächst nicht betrachtet werden soll. Der Wert (ggf. Betrag) einer solchen Zahl ist die Summe aus den mit ihrem jeweiligen Stellenwert multiplizierten Ziffern.

Eine ganze Zahl (Integer) mit der Ziffernfolge   an–1 an–2 ... a1 a0   hat den Wert
N = Summe(ai*B^i) von i = 0 bis n-1
 
und eine gebrochene (reelle) Zahl (Real) mit der Ziffernfolge   an–1 an–2 ... a1 a0 , a–1 ... am   hat den Wert
R = Summe(ai*B^i) von i = -m bis n-1

Wie bereits eingangs erwähnt, gilt diese Berechnung eines Zahlenwertes in einem polyadischen Zahlensystem für jede beliebige Basis, d.h. gleichermaßen für das im täglichen Leben gewohnte Dezimalsystem mit der Basis 10 sowie für das in Computern fast ausschließlich verwendete Binärsystem mit der Basis 2. Die Basis kann aber auch jede andere Zahl sein. Zur kompakteren Notierung von Binärzahlen sind außerdem noch das Oktalsystem mit der Basis 8 und das Hexadezimalsystem mit der Basis 16 gebräuchlich. Bei den Babyloniern gab es sogar ein solches Zahlensystem mit der Basis 60. Bei gegebener Basis sind B verschiedene Ziffern von 0 (null) bis B–1 erforderlich. Das sind im Dezimalsystem mit B = 10 die wohlbekannten Ziffern 0 – 9. Im Binärsystem mit B = 2 sind nur die beiden Ziffern 0 und 1 erforderlich, die in Rechnern technisch besonders einfach und störsicher dargestellt werden können. Entsprechend braucht das Oktalsystem (B = 8) die 8 Ziffern 0 – 7 und im Hexadezimalsystem sind 16 verschiedene Ziffern erforderlich, wofür die Ziffern 0 – 9 mit den Großbuchstaben A – F ergänzt werden (Tabelle 1-1). Das babylonische Zahlensystem mit B = 60 hat sich auf Dauer nicht halten können, weil es 60 verschiedene Ziffern braucht, die entweder kompliziert zu schreiben oder schlecht zu unterscheiden sind. Tatsächlich hatte dieses Zahlensystem nur 59 verschiedene Ziffern, weil seinerzeit die 0 als Platzhalter noch nicht bekannt war und tatsächlich durch einen entsprechenden Leerraum in einer Zahl dargestellt wurde. Das dürfte bei mehreren aufeinanderfolgenden Nullen eine sorgfältige Plazierung der Ziffern erfordet haben.

 
Tabelle 1-1: Polyadische Zahlensysteme mit verschiedener Basis

Zahlen-
basis
Binär
2
Ternär
3
Oktal
8
Dezimal
10
Hexadez.
16
Code 0     0     0     0     0    
1     1     1     1     1    
10     2     2     2     2    
11     10     3     3     3    
100     11     4     4     4    
101     12     5     5     5    
110     20     6     6     6    
111     21     7     7     7    
1000     22     10     8     8    
1001     100     11     9     9    
1010     101     12     10     A    
1011     102     13     11     B    
1100     110     14     12     C    
1101     111     15     13     D    
1110     112     16     14     E    
1111     120     17     15     F    
10000     121     20     16     10    

Wenn Zahlen in verschiedenen polyadischen Systemen behandelt werden, setzt man in der Mathematik die betreffende Zahl in Klammern und schreibt die Basis dahinter tiefgestellt an die Klammer. Dabei wird die Basis immer im Dezimalsystem notiert. Wie aus Tabelle 1-1 ersichtlich, hat die Basis B immer die Ziffernfolge 10, wenn sie in ihrem eigenen Zahlensystem geschrieben wird.

B =   (2)10 = (10)2    Binärsystem
B =   (3)10 = (10)3    Ternärsystem
B =   (8)10 = (10)8    Oktalsystem
B = (10)10 = (10)10   Dezimalsystem
B = (16)10 = (10)16   Hexadezimalsystem

In den folgenden Beispielen wird die Dezimalzahl 157 in verschiedenen Zahlensystemen mit einer anderen Basis angegeben.

Binärsystem [Stellenwerte: ... 256 / 128 / 64 / 32 / 16 / 8 / 4 / 2 / 1]
(157)10 = 1·27 + 0·26 + 0·25 +1·24 +1·23 + 1·22 +0·21 +1·20 = (10011101)2
Oktalsystem [Stellenwerte: ... 512 / 64 / 8 / 1]
(157)10 = 2·82 + 3·81 + 5·80 = (235)8
Hexadezimalystem [Stellenwerte: ... 256 / 16 / 1]
(157)10 = 9·161 + D·160 = (9D)16
Ternärsystem [Stellenwerte: ... 243 / 81 / 27 / 9 / 3 / 1]
(157)10 = 1·34 + 2·23 + 2·32 +1·31 +1·30 = (12211)3

Das Ternärsystem hat kaum praktische Bedeutung und ist hier nur als Beispiel angegeben, daß eine beliebige natürliche Zahl die Basis eines polyadischen Zahlensystems sein kann. Neben dem Dezimalsystem im täglichen Leben hat das Binärsystem in der Digitaltechnik große Bedeutung. Man sieht jedoch schon an diesem einfachen Beispiel, daß größere Binärzahlen unhandlich lang werden. Deshalb sind sie für einen Menschen nur schwer zu erfassen, wenn er sich, z.B. als Digitaltechniker, doch einmal damit beschäftigen muß. Wegen 2³ = 8 und 24 = 16 können ohne weitere Umrechnung Dreiergruppen von Bits als Oktalziffern bzw. Vierergruppen als Hexadezimalziffern notiert werden. Dabei ist immer von rechts, d.h. mit der Einerstelle zu beginnen.

     dezimal 157 = 1 0 0 1 1 1 0 1   binär
                 =  2 |  3  |  5  |  oktal       (Ziffern 0 ... 7)

     dezimal 157 = 1 0 0 1 1 1 0 1   binär
                 =    9   |   D   |  hexadezimal (Ziffern 0 ... 9 und A ... F)

Da Binärdaten üblicherweise in Bytes (zu 8 Bit) gruppiert sind, hat sich dafür seit Jahren die hexadezimale Notierung durchgesetzt, denn ein Byte entspricht genau zwei Hexadezimalziffern. Dabei sind statt der Großbuchstaben A ... F oft auch die entsprechenden Kleinbuchstaben a ... f zugelassen. Sofern in der Digitaltechnik die Basis einer Zahl nicht zwingend festgelegt ist, wird dort jedoch meistens nicht die o.a. mathematische Notierung mit der anschließenden tiefgestellten Zahlenbasis verwendet. Um die Formatierung (für Tiefstellung) zu vermeiden, findet man oft eine der folgenden Abkürzungen als Präfix oder Suffix an der betreffenden Zahl.

  dezimal:
binär:
oktal:
hexadezimal:
dez bzw. ohne Kennzeichnung
bin oder b
okt oder o
hex, h oder x

Manchmal werden jedoch auch andere Sonderzeichen verwendet. Bei Bedarf muß man also beachten, in welcher Form Zahlen einzugeben bzw. zu kennzeichnen sind, zumal es unter Umständen auch Kurzformen geben kann, z.B. bei den hexadezimalen Angaben bestimmter Farben in HTML.   [^ Inhalt]

 
2. Rechenregeln

Die Rechenregeln sind für alle polyadischen Zahlensysteme geich, d.h. die stellenweisen schriftlichen Rechenverfahren, die für das Dezimalsystem aus der Schule bekannt sind, können sinngemäß auch in allen anderen polyadischen Zahlensystemen angewendet werden. Bei mehrstelligen Zahlen ist lediglich zu beachten, daß immer dann ein Übertrag in die nächsthöhere Stelle auftritt, wenn die jeweilige Basis B in der aktuellen Stelle erreicht oder überschritten wird.   [^ Inhalt]

 
2.1 Grundrechenarten

In den ersten Schuljahren hatten wir alle Gelegenheit, folgende vier Grundrechenarten zu lernen und zu üben:

  1. Addition:   a + b = s
      i. Augend  +  Addend  =  Summe
      ii. Summand  +  Summand  =  Summe
     
  2. Subtraktion:   ab = d   (Umkehrung der Addition)
    Minuend – Subtrahend = Differenz
     
  3. Multiplikation:   a · b = p
      i. Multuiplikand  ·  Multiplkator  =  Produkt
      ii. Faktor  ·  Faktor  =  Produkt
     
  4. Division   a : b = q   (Umkehrung der Multiplikation)
    Dividend : Divisor = Quotient

Die Reihenfolge der beiden Operatoren a und b ist bei der Addition (1.) und bei der Multiplikation (3.) vertauschbar. Daher werden sie meistens als Summanden (1.ii) bzw. gelegentlich als Faktoren (3.ii) bezeichnet. Diese Vertauschung ist zwar mathematisch völlig korrekt, in der Rechentechnik jedoch durchaus zu unterscheiden. Bei der schriftlichen Multiplikation (3.i) wird zunächst für jede Stelle des Multiplikators b das betreffende Teilprodukt des Multiplikanden a bestimmt, bevor dann alle Teilprodukte stellenrichtig addiert werden. Da die Anzahl der Teilprodukte den von null verschidenen Stellen des Multiplikators entspricht, rechnet man zweckmäßigerweise mit dem größeren Faktor, der mehr Stellen hat, als Multiplikand und dem kleineren Faktor, der weniger Stellen hat, als Multiplikator. Wer sich nicht mehr an diesen Schulstoff erinnert, kann das betreffende Zahlenbeispiel im nächsten Abschnitt nachvollziehen. Beim schriftlichen Berechnen einer Summe (1.i) ist die Zuordnung der beiden Summanden a und b zu Augend bzw. Addend beliebig, wenngleich das in der maschinellen Rechentechnik manchmal bedeutsam sein kann. Bei den Umkehrrechnungen Subtraktion (2.) und Division (4.) dürfen die Operanden a und b nicht vertauscht werden. Ansonsten würde sich die negative Differenz (ba = – d ) bzw. der Kehrwert des Quotienten (b : a = 1/q) ergeben.

Zu Zeiten des Rechenmeisters Adam Ries(e), der diese Grundrechenarten im 16. Jahrhundert eingeführt hat, mußte zunächst das Abzählen erlernt werden, das damals noch nicht Allgemeingut war. Mit dessen Hilfe ist es auch heute noch möglich, die Ergebnisse von Zahlenrechnungen zu überprüfen, solange die Zahlen dafür nicht unhandlich groß sind. In meiner eigenen Kinderzeit nach dem Zweiten Weltkrieg waren sog. Kinderrechenmaschinen (Abakusse, Rechenrahmen) weit verbreitet, mit denen man das Abzählen und die Grundrechenarten spielerisch lernen konnte. Bei diesen Geräten waren meistens 10 × 10 farbig markierte Kugeln auf 10 Stäben verschiebbar angeordnet, um auf einfache Weise natürliche Zahlen bis 100 darzustellen und die vier Grundrechenarten durch Verschieben und/oder Abzählen anschaulich darzustellen. Das eigentliche Rechnen mit Zahlen (im Dezimalsystem) wurde dann in den ersten Schuljahren gelernt und geübt.   [^ Inhalt]

 
a) Dezimalsystem

Um im Kopf, oder bei längeren Zahlen (mit Papier und Stift) schriftlich, einigermaßen effektiv rechnen zu können, muß man für das alltägliche Dezimalsystem die folgende Additions- und die Multiplikationstabelle zumindest für einstellige Zahlen auswendig gelernt haben.

               Additionstabelle                      Multiplikazionstabelle*)
                  s = a + b                                 p = a x b

     \a  0  1  2  3  4  5  6  7  8  9          \a  0  1  2  3  4  5  6  7  8  9
     b\+-----------------------------          b\+-----------------------------
     0 | 0  1  2  3  4  5  6  7  8  9          0 | 0  0  0  0  0  0  0  0  0  0
     1 | 1  2  3  4  5  6  7  8  9 10          1 | 0  1  2  3  4  5  6  7  8  9
     2 | 2  3  4  5  6  7  8  9 10 11          2 | 0  2  4  6  8 10 12 14 16 18
     3 | 3  4  5  6  7  8  9 10 11 12          3 | 0  3  6  9 12 15 18 21 24 27
     4 | 4  5  6  7  8  9 10 11 12 13          4 | 0  4  8 12 16 20 24 28 32 36
     5 | 5  6  7  8  9 10 11 12 13 14          5 | 0  5 10 15 20 25 30 35 40 45
     6 | 6  7  8  9 10 11 12 13 14 15          6 | 0  6 12 18 24 30 36 42 48 54
     7 | 7  8  9 10 11 12 13 14 15 16          7 | 0  7 14 21 28 35 42 49 56 63
     8 | 8  9 10 11 12 13 14 15 16 17          8 | 0  8 16 24 32 40 48 56 64 72
     9 | 9 10 11 12 13 14 15 16 17 18          9 | 0  9 18 27 36 45 54 63 72 81

                                                    *) = kleines Einmaleins

Die Additionstabelle hat man zwar nicht explizit auswendig gelernt, sondern sich bei Additions- und Subtraktionsrechnungen "so nebenbei" eingeprägt. In der Multiplikationstabelle erkennen wir jedoch das wohlbekannte kleine Einmaleins wieder, das zu meiner Zeit in der Grundschule schrittweise gepaukt und immer wieder abgefragt wurde, bis es wirklich saß. Allerdings reicht das kleine Einmaleins üblicherweise nicht von 0 × 0 bis 9 × 9, sondern von 1 × 1 bis 10 × 10. Für das stellenweise Rechnen im Dezimalsystem sind jedoch die o.a. Tabellen von 0 bis 9 zweckmäßiger. Da die Reihenfolge der Summanden bzw. der Faktoren a und b beliebig ist, d.h. vertauscht werden kann, sind beide Tabellen spiegelbildlich zur Hauptdiagonalen. In der Hauptdiagonalen stehen bei der Additionstabelle die 10 geraden Zahlen von 0 bis 18, und bei der Multiplikationstabelle die 10 Quadratzahlen von 0 bis 81. Zweistellige Ergebnisse in den Tabellen bedeuten, daß die erste Ziffer als Übertrag in die nächsthöhere Dezimalstelle des Resultats zu berücksichtigen ist. Das ist bei der Addition von zwei Dezimalzahlen maximal eine 1, bei der Multiplikation maximal eine 8. Zum Veranschaulichen bzw. zum Auffrischen der Erinnerung soll jede Grundrechenart an einem Zahlenbeispiel dargestellt werden.

Addition

a 2355 Augend (1. Summand)
+   b 157 Addend (2. Summand)
    1 1    Übertrag
= s 2512 Summe

Zunächst schreibt man die zu addierenden Summanden stellenrichtig untereinander, d.h. die natürlichen Zahlen in diesem Beipiel rechtsbündig, Dezimalbrüche mit unterschiedlich vielen Nachkommastellen so, daß deren Kommas übereinander stehen. Um das Ergebnis von den Summanden abzutrennen, zieht man unter dem letzten Summanden einen Strich, über dem man etwas Platz für mögliche Überträge läßt. Dann beginnt man, von rechts nach links, also mit der Einerstelle (0), stellenweise zu addieren. Bei wenig Übung oder für spätere Kontrollrechnungen kann man die Überträge in die jeweils nächsthöhere Stelle dort unmittelbar über den Strich schreiben, jedoch als kleinere Ziffern, damit sie nicht mit einem weiteren Summanden verwechselt werden. Nach augeführter Addition "ergibt sich unter dem Strich" die Summe, eine Formulierung, die in dieser Form in die Umgangssprache eingegangen ist. Die schriftliche Addition, deren Ergebnisse an entsprechender Stelle notiert werden, läuft in Gedanken folgendermaßen ab, hier von oben nach unten statt von rechts nach links mit dem Eingangsübertrag c0:

     St| a   b   c   zs |      s                   Legende (Spaltenbezeichnungen):
     --+----------------+----------------     St = Stelle (0 = Einer bis 3 = Tausender)
     0 | 5 + 7 + 0 = 12 | s0 = 2, c1 = 1      a  = Augend = 1. Summand
     1 | 5 + 5 + 1 = 11 | s1 = 1, c2 = 1      b  = Addend = 2. Summand
     2 | 3 + 1 + 1 =  5 | s2 = 5, c3 = 0      c  = Übertrag [Carry] (zu addieren)
     3 | 2 + 0 + 0 =  2 | s3 = 2, c4 = 0      zs = Zwischensumme (nur intern)
                                              s  = Summe (mit stellenrichtig
                                                   addierten Überträgen c)

Bei der Addition von mehr als zwei Ziffern ist hinter der Zwischensumme (zs) eine Trennlinie (|) eingefügt, um zu verdeutlichen, daß die weiteren Angaben nicht als durchgängige Gleichung zu verstehen sind. Ein Routinier wird die Überträge meistens nicht hinschreiben, sondern nur "im Sinn" behalten und auf seinem Recchenblock von unten nach oben addieren, damit er mit den ggf. im Sinn behaltenen Überträgen beginnen kann, was natürlich nichts am Ergebnis ändert:

     St| c   b   a   zs |      s          Legende (wie oben)
     --+----------------+---------------
     0 | 0 + 7 + 5 = 12 | s0 = 2, c1 = 1  Summe 2, 1 im Sinn
     1 | 1 + 5 + 5 = 11 | s1 = 1, c2 = 1  Summe 1, 1 im Sinn
     2 | 1 + 1 + 3 =  5 | s2 = 5, c3 = 0  Summe 5, 0 im Sinn
     3 | 0 + 0 + 2 =  2 | s3 = 2, c4 = 0  Summe 2, 0 im Sinn (Ende der Rechnung)

 
Subtraktion

a 2355 Minuend
–   b 157 Subtrahend
    1 1    Übertrag (Geborgte)
= d 2198 Differenz

Zunächst schreibt man die zu subtrahierenden Summanden stellenrichtig untereinander, d.h. die natürlichen Zahlen in diesem Beipiel rechtsbündig, Dezimalbrüche mit unterschiedlich vielen Nachkommastellen so, daß deren Kommas übereinander stehen. Um das Ergebnis von den zu subtrahierenden Zahlen abzutrennen, zieht man unter dem Subtrahenden einen Strich, über dem man etwas Platz für mögliche Überträge läßt. Dann beginnt man, von rechts nach links, also mit der Einerstelle (0), stellenweise zu subtrahieren. Bei wenig Übung oder für spätere Kontrollrechnungen kann man die Überträge in die jeweils nächsthöhere Stelle dort unmittelbar über den Strich schreiben, jedoch als kleinere Ziffern, damit sie nicht mit einem weiteren Subtrahenden verwechselt werden. Nach augeführter Subtraktion "ergibt sich unter dem Strich" die gesuchte Differenz. Die schriftliche Subtraktion, deren Ergebnisse an entsprechender Stelle notiert werden, läuft in Gedanken folgendermaßen ab, hier von oben nach unten statt von rechts nach links mit dem Eingangsübertrag c0:

     St| a   b   c | ze   b   d              Legende (Spaltenbezeichnungen):
     --+-----------+---------------------     St = Stelle (0 = Einer bis 3 = Tausender)
     0 | 5 - 7 - 0 | 15 - 7 = 8, c1 = 1      a  = Minuend
     1 | 5 - 5 - 1 | 14 - 5 = 9, c2 = 1      b  = Subtrahend
     2 | 3 - 1 - 1 |  2 - 1 = 1, c3 = 0      c  = Übertrag [Carry bzw. Borrow]
     3 | 2 - 0 - 0 |  2 - 0 = 2, c4 = 0           (stellenweise von a zu subtrahieren)
                                             ze = Zwischenergebnis (a - c)
                                             d  = Differenz (mit stellenrichtig
                                                  suntrahierten Überträgen c)

Ein Routinier wird die Überträge meistens nicht hinschreiben, sondern nur "im Sinn" behalten. Er wird auf seinem Recchenblock nicht wirklich subtrahieren, sondern jede Stelle der Differenz d als Ergänzung des Subrahenden b zum Minuenden a bilden. Dabei addiert er zunächst die im Sinn behaltenen Überträge zum Subtrahenden, anstatt sie vom Minuenden abzuziehen, was natürlich nichts am Ergebnis ändert:

     St| a   b   c |  a  ze   d            Legende (wie oben):
     --+-----------+---------------------  ze = Zwischenergebnis (b + c)
     0 | 5 - 7 - 0 | 15 = 7 + 8, c1 = 1    Differenz 8, 1 im Sinn
     1 | 5 - 5 - 1 | 15 = 6 + 9, c2 = 1    Differenz 9, 1 im Sinn
     2 | 3 - 1 - 1 |  3 = 2 + 1, c3 = 0    Differenz 1, 0 im Sinn
     3 | 2 - 0 - 0 |  2 = 0 + 2, c4 = 0    Differenz 2, 0 im Sinn (Ende der Rechnung)

 
Multiplikation

a × b  = 2355 × 157  = Multiplikand × Multiplikator = Produkt p
16485 Multiplikand ×     7
11775   Multiplikand ×   50
2355     Multiplikand × 100
           1 1 1       Übertrag
p  = 369735 Produkt

Wenn die beiden zu multiplitierenden Faktoren unterschiedlich viele Stellen haben, wählt man zweckmäßigerweise die kürzere Zahl als Multiplikator und schreibt beide Zahlen entsprechend dem vorstehenden Schema hin. Dann wird der Multiplikand der Reihe nach entsprechend dem kleinen Einmaleins mit den einzelnen Stellen des Multiplikators multipliziert. Diese Teilprodukte werden in richtiger Stellenzuordnung, d.h. rechtsbündig unter die betreffende Stelle des Multiplikators geschrieben. Dieses Verfahren erfaßt die Zehnerpotenzen des Multiplikators, ohne daß die folgenden Nullen der Teilprodukte hingeschrieben werden müssen. Das Produkt ergibt sich durch stellenrichtige Addition aller Teilprodukte. Ob man mit der ersten oder, wie hier, mit der letzten Stelle den Multiplikators beginnt, ändert nur die Reihenfolge der Teilprodukte, aber nicht das Ergebnis. In der (mechanischen oder elektronischen) Rechentechnik wird meistens mit der letzten Stelle des Multiplikators begonnen. Weil dort jedes Teilprodukt sofort saldiert wird, ist es zweckmäßig, wenn nach dem ersten Schritt die letzte Stelle des Produkts bereits feststeht und mit jedem weiteren Teilprodukt die nächsthöhere Stelle. Dadurch wirken sich mögliche Überträge auf entsprechend weniger Stellen aus. Bei mechanischen Rechenmaschinen führt das zu geringerer Materialbelastung und bei elekronischen Rechnern zu kürzerer Signallaufzeit, d.h. zu höherer Rechengeschwindigkeit.

 
Division

a : b  = Dividend   : Divisor = Quotient q
2355   : 157      = 15
157  
785
785 (= 157 × 5)
0

Die schrifliche Division wird sowohl mit Papier und Stift als auch in klassischen Rechenmaschinen nach dem ovorstehenden Schema schrittweise durchgeführt. Zunächst wird geprüft, wie weit links der Divisor in dem Dividenden enthalten ist. Das ist er bei diesem Zahlenbeispiel linksbündig genai 1 Mal. Damit steht sie erste Stelle des Quotienten fest. Man schreib also 1 × 157 = 157 linksbündig unter den Dividenden und zieht dieses Teilprodukt stellenrichtig ab. Der Divisionsrest 78 < 157 zeigt an, daß die erste Stelle korrekt bestimmt worden ist. Dann wird die nächste Stelle den Dividenden (hier 5) hinter den Divisionsrest gescgrieben, woraus sich für den nächste Schritt die Zahl 785 ergibt, die durch 157 zu teilen ist. Das geht genau 5 Mal, denn 5 × 157 = 785. Damit ist 5 die nächste Stelle des Quotienten. Nach dem Abziehen des Teilorodukts vom vollständigen Divisionsrest ergibt sich 0 (Null), d.h. die Division ist "aufgegangen", weil der Dividend eine ganzzahliges Vielfaches (das 15-fache) des Divisors ist.  [^ Inhalt]

 
b) Binärsystem

Wie oben bereits erwähnt, ist das Binärsystem ein polyadisches Zahlensystem mit der Basis 2. Dort gibt es nur die beiden Ziffern 0 und 1, wodurch die Additions- und die Multiplikationstabelle gegenüber dem Dezimalsystem erheblich kleiner sind:

        Additionstabelle        Multiplikazionstabelle*)
           s = a + b                   p = a x b

          \a   0    1                 \a   0   1
          b\+---------                b\+--------
          0 |  0    1                 0 |  0   0
          1 |  1   10                 1 |  0   1
                   ⇑            *) = kleines Einmaleins
                   Carry
                   Übertrag in die nächsthöhere Stelle

Aus der Additionstabelle sind Summe s und Übertrag c der vier Eingangskombinationen einer Binärstelle ersichtlich:

  1. 0 + 0 = 0
  2. 0 + 1 = 1
  3. 1 + 0 = 1
  4. 1 + 1 = 210 = 102 = Summe 0, Übertrag 1

Damit entspricht die Summe s der Exclusiv-Oder-Funktion bzw. der Antivalenz-Funktion, denn sie ist = 1, wenn die beiden Summanden verschieden sind und = 0, wenn sie gleich sind. Der Übertrag in die nächste Stelle entspicht der logischen UND-Funktion. Die Multiplikationstabelle für Binärzahlen ist noch einfacher, denn das Produkt p wird nur dann = 1, wenn beide Faktoren a = b = 1 sind. In den drei anderen Fällen ist p = 0. Das entspricht der logischen UND-Funktion.

Die o.a. Additionstabelle gilt jedoch in dieser einfachen Form nur für die niederwertigsten Stellen a0 und b0 der beiden Summanden a und b. Außer der Summenstelle s0 wird auch der Übertrag (Carry) c1 in die nächsthöhere Stelle mit der Wertigkeit 21 erzeugt. Dieser Übertrag muß in allen höherwertigen Stellen (mit dem allgemeinen Stellenwert 2i für i > 0) außer ai und bi als dritte Binärziffer ci verarbeitet werden. Im Gegensatz zu einem Halbaddierer, der nur 2 Ziffern a0 und b0 addieren kann, wird eine Schaltung, die auch einen Eingangsübertrag ci als dritte Eingangsvariable verarbeitet, als Volladdierer bezeichnet. In der folgenden Tabelle sind für Halb- und Volladdierer die beiden Augangsvariablen Übertrag c1 und s0 bzw. ci+1 und si dargestellt. Für ci = 0 (obere Hälfte der Tabelle) sind die Ausgangsfunktionen für Halb- und Volladdierer identisch. ci = 1 (rechter unterer Teil der Tabelle) ist nur beim Vollsddierer möglich. In jedem Fall sind die beiden Ausgangsvariablen Übertrag c1 und s0 bzw. ci+1 und si zwei Ziffern einer Binärzahl, die angibt, wie viele der Eingangsvariablen ci, bi, ai = 1 sind, nämlich 00 (= 0), 01 (=1), 10 (= 2) oder 11 (= 3).

Halbaddierer   Volladdierer
b0 a0 c1 s0   ci bi ai ci+1 si
0 0 0 0   0 0 0 0 0
0 1 0 1   0 0 1 0 1
1 0 0 1   0 1 0 0 1
1 1 1 0   0 1 1 1 0
  1 0 0 0 1
  1 0 1 1 0
  1 1 0 1 0
  1 1 1 1 1

Bei der Addition von zwei Binärzahlen kann jeder Übertrag maximal 1 werden, d.h. er wirkt sich unmittelbar nur auf die nächsthöhere Stelle aus. Deshalb können Binärzahlen mit einer beliebigen Stellenzahl mit solchen Volladdierern addiert werden. Bei einem Paralleladdierer ist für jede Binärstelle ein solcher Volladdierer vorhanden, deren Übertragsausgänge mit den betreffenden Eingängen der nächthöheren Stelle verbunden sind. Da die Signallaufzeit in elektronischen Schaltungen durchaus endlich ist, wird die berechnete Summe s erst gültig, nachdem ggf. ein Übertrag von der niedrigsten bis zur höchten Stelle durchgelaufen ist (ripple carry). Mit verschiedenen Schaltungsvarianten ist immer wieder versucht worden, diese entscheidende Laufzeit des Übertrags bei der Addidion von größeren Binarzahlen zu verkürzen. Bei heutigen hochintegrierten Schaltungen ist das alles auf den betreffenden Chips vorhanden, und der Anwender merkt davon kaum noch etwas. – Zu Zeiten, als es noch keine integrierten Schaltungen gab und die Hardware noch aus einzelnen Transistoren (oder gar Röhren) aufgebaut wurde, wurden die beiden Eingangszahlen a und b oftmals bitweise, d.h. seriell, mit dem niederwertigsten Bit voran durch einen nur 1 Bit breiten Volladdierer getaktet, wobei der sich ergebende Übertrag in einem Flipflop zwischengewpeichert und im nächsten Takt als Eingangsvariable für die Addition der nächsten Stelle eingespeist wurde. So etwas gab es noch bis gegen Ende des 20. Jahrhunderts, aber inzwischen dürfte diese serielle Addition nur noch historischen Wert haben.

Für die folgenden Beispiele der vier Grundrechenarten im Binärsystem werden bewußt kleine Zahlen mit übersichtlicher Stellenzahl verwendet, an deren Dezimalwert die Rechnung leicht überprüft werden kann. Längere Folgen von Nullen und Einsen entsprechend großer Binärzahlen werden erfahrungsgemäß zu schnell unübersichtlich. Die Rechenschemata sind jedoch für alle polyadischen Zahlensystteme gleich, d.h. im Binärsystem genau so wie im Dezimalsystem. Es ist lediglich zu berücksichtigen, daß im Binärsystem in jeder Stelle beireits ab der Summe 2 = (10)2 ein Übertrag in die nächsthöhere Stelle entsteht, und nicht erst ab der Summe 10 = (10)10 (im Dezimalsystem). Damit sollten die Rechnschritte der beiden folgenden Zahlenbeispiele zur Addition und Subtraktion von zwei Binärzahlen unmittelbar verständlich sein.

Addition

a (6)10   0110 Augend (1. Summand)
+   b (7)10 0111 Addend (2. Summand)
  1           1 1       Übertrag
= s (13)10 1101 Summe

 
Subtraktion

a (26)10 11010 Minuend
–   b (11)10 01011 Subtrahend
                  1 1 1 1    Übertrag (Geborgte)
= d (15)10 01111 Differenz

 
Multiplikation

a × b  = (7)10 × (6)10  = 111 × 110  = Multiplikand × Multiplikator = Produkt p
000 Multiplikand ×     0
111   Multiplikand ×   10   (2)10
111     Multiplikand × 100   (4)10
       1 1 1       Übertrag
p  = (42)10  = 101010 Produkt
42      = 32+8+2  

Die Multiplikation ist im Binärsystem deutlich einfachen als im Dezimalsystem, weil der Multiplikand abhängig von der aktuallen Stelle des Multiplikators nur mit 0 oder 1 multipliziert werden muß. Es müssen also lediglich Nullen oder der unveränderte Multiplikand stellenrichtig hingeschrieben und addiert werden. Im Gegensatz zum schriftlichen Rechnen auf Papier wird beim maschinellen Rechnen jedes Teilprodukt sofort stellenrichtig zu einer Zweischensumme addiert, die zum Schluß das gesuchte Produkt ergibt.Diese Methode hat zwei Vorteile, denn es müssen jedes Mal nur 2 Zahlen addiert und nicht alle Teilprodukte zwischengespeichert werden.

 
Division

a : b  = Dividend   : Divisor = Quotient q
(20)10   : (4)10    = (5)10
10100   : 100     = 101
100    
10  
00  
100
100
0

Auch die schrittweise schriftliche Division ist im Binärsystem einfacher als im Dezimalsystem, weil die Stellen des Quotienten nur 0 oder 1 sein können. Deshalb ist zum Bestimmen der stellenrichtig abzuziehenden Teilprodukte hierfür die Kenntnis des "kleinen Einmaleins" (im Dezimalsystem) nicht erforderlich.   [^ Inhalt]

 
2.2 Komplementdarstellung

Das Subtrahieren von zwei Zahlen mit Papier und Stift erscheint uns nicht besonders schwierig, weil wir es (im Dezimalsystem) gewohnt sind. In einem Rechner wäre dafür jedoch zusätzlich zum Addierer ein Subtrahierer erforderlich, sofern es nicht gelingt, auf einfache Weise negative Zahlen darzustellen, die dann einfach addiert werden können. Ein Weg dorthin ist die Darstellung negativer Zahlen als deren Komplment. Dieser Zusammenhang kann in folgender Gleichung dargestellt weden:

d = xy = x + (Cy) – C

Dabei ist C eine Konstante und (Cy) das Komplement von y zu dieser Kostanten C. Diese Gleichung erweckt den Eindruck, als würde die gestellte Aufgabe dadurch komplizierter statt einfacher. Die Konstante C kann jedoch so gewählt werden, daß sowohl die Komplementbildung (Cy) als auch das Entfernen der Konstanten C am Ende der Gleichung ohne Subtraktion möglich sind. Bei einer n-stelligen Zahl in einem polyadischen Zahlensystem mit der Basis B wählt man zweckmäßigerweise:

C   = Bn     Dann ist C ist eine 1 mit n Nullen, d.h. mit n Stellen nicht mehr darstellbar.
 
C-1 = Bn – 1     ist die größte mit n Ziffern darstellbare Zahl (alle Ziffern = B – 1).

Dabei ist n normalerweise nicht die tatsächlich benutzte Stellenzahl, sondern die maximale Anzahl der Stellen, mit der die Zahlen in einer Rechenmaschine dargestellt werden (Wortbreite der Rechenregister). Dabei fällt die führende 1 von Bn als Übertrag aus dem darstellbaren Zahlenbereich links heraus. Dadurch wird der Term ' – C ' in der o.a. Gleichung ohne Subtraktionsrechnung entfernt. Formal addiert man dabei also modulo C, das heißt es werden nur die n Stellen (Reste) unterhalb von C weiterverarbeitet. Das Komplement

(Cy) = (Bny) = (C-1 – y) + 1             mit   C-1 = Bn – 1

ist, wie bereits oben erwähnt, die größte n-stellige Zahl, die aus n der höchsten Ziffern B – 1 eines polyadischen Zahlensystems mit der Basis B besteht. Damit ist (C-1 – y) das sogenannte B–1-Komplement, das durch ziffernweise Ergänzung einer mehrstelligen Zahl zur höchsten Ziffer B – 1 dieses Zahlensystems gebildet werden kann, und zwar ohne Subtraktionsrechnung. Zur Unterscheidung wird das Komplement (Bny) umgangssprachlich als B-Komplement bezeichnet, obwohl es eigentlich Bn-Komplement heißen müßte. Beim Rechnen mit Zahlen in Komplementdarstellung ist zu bedenken, daß den Bn Kombinationen von n Ziffern sowohl die positiven als auch die negativen Zahlen (in Komplementdartellung) zugeordnet werden, weil es kein zusätzliches Vorzeichen gibt. Damit gibt es in Komplementdarstellung 2 Wertebereiche von je ½ × Bn positiven Zahlen (von 0 bis ½ × Bn – 1) und ½ × Bn negativen Zahlen (von ½ × Bn ⇔ – ½ × Bn bis Bn – 1 ⇔ – 1). Das Rechnen mit Zahlen in Komplementdarstellung wird in den nächsten Abschnitten am Beispiel des Dezimalsystems und des Binärsystems anschaulich erläutert.   [^ Inhalt]

 
a) Dezimalsystem

Diese Komplementdarstellung soll zunächt an Zahlenbeispielen im vertrauten Desimalsystem mit einem Bereich von n = 3 Dezimalstellen plausibel dargelegt werden.

B = 10               Dezimalsystem
n =   3               Dezimalstellen (als Beispiel gewählt)
C = Bn = 103 = 1000 verschiedene Zahlen (000 – 999)

Mit 3 Dezimalstellen sind 103 = 1000 verschiedene Zahlen darstellbar. Für ausschließlich natürliche Zahlen (positive ganze Zahlen) sind das die Werte von 0 bis 999. Für die Komplementdarstellung wird dieser Wertebereich jedoch halbiert, um 500 positive Zahlen y von 0 bis 499 und 500 negative Zahlen – y von – 1 bis – 500 darzustellen, denen die entsprechenden Komplemente – y = Bn y von 999 bis 500 zugeordnet werden. In Tabelle 2-1 sind die positiven und die negativen Zahlen (im 10-er-Komplement) aufgelistet. Zusätzlich sind die Zahlen auch als 9-er-Komplemenet angegeben, aus dem ersichtlich ist, daß dessen die jeweilige Ergänzung der positiven Ziffern zu B – 1 = 9 sind. Das 10-er-Komplement ergibt sich daraus durch Addition einer '1'. Falls ein im 10-er-Komplement vorliegendes Ergebnis interpretiert werden soll, läßt sie sich auf dieselbe Methode (9-er-Komplement + 1) in eine positive Zahl umwandeln. Da Tabelle 2-1 für alle 500 Wertepaare zu lang geworden wäre, sind nur die 6 niedrigsten und die 6 höchten Wertepaare angegeben, die zur Anschauung völlig ausreichen.

 
Tabelle 2-1: Komplementdarstellung im Dezimalsystem (n = 3)

Wert
neg.
10-er-
Kompl.
9-er
Kompl.
pos.
Zahl
Wert
pos.
+ 0 000 999 000 + 0
– 1 999 998 001 + 1
– 2 998 997 002 + 2
– 3 997 996 003 + 3
– 4 996 995 004 + 4
– 5 995 994 005 + 5
··· ··· ··· ··· ···
– 495 505 504 495 + 495
– 496 504 503 496 + 496
– 497 503 502 497 + 497
– 498 502 501 498 + 498
– 499 501 500 499 + 499
– 500 500 499    

Um mehrere Rechenbeispiele mit Komplementen vorzusführen, werden die drei positiven Zahlen x = 270; y = 164 und z = 358 gewählt. Damit können die in Tabelle 2-2 angegebenen sechs systematisch verschidenen Fälle der vorzeichengerechten Addition bei der Komplementrechnung dargestellt werden.

 
Tabelle 2-2: Die 6 verschiedenen Fälle
der vorzeichengerechten Addition

verschiedene Vorzeichen
Differenzbildung
s1 = + xy
s1 ≥ 0
s2 = + yx
s2 < 0
gleiche Vorzeichen
ohne Bereichsüberschreitung
s3 = + x + y
s3 < 500
s4 = – xy
s4 ≥ – 500
gleiche Vorzeichen
mit Bereichsüberschreitung
s5 = + x + z
s5 ≥ 500
s6 = – xz
s7 < – 500

Die angegebene Bereichchsgrenze von 500 für 3-stellige Dezimalzahlen lautet allgemein ½ × Bn = ½ × 103. Außer durch die mathematische Notierung in Tabelle 2-2 können diese 6 verschiedenen Fälle auch in Worten beschrieben werden:

1 & 2: Verschiede Vorzeichen der Summanden
Bei verschiedenen Vorzeichen der Summanden kann die Summe positiv oder negativ sein. Eine Bereichsüberschreitung kann nicht auftreten, weil der Betrag der Summe in jedem Fall kleiner ist als der größere Betrag eines der Summanden.
3 & 4: Gleiche Vorzeichen der Summanden, ohne Bereichsüberschreitung
Bei gleichen Vorzeichen der Summanden hat die Summe dasselbe Vorzeichen. Diese beiden Fälle sind Beispiele, bei denen keine Bereichsüberschreitung auftritt, weil die Summe innerhalb des darstellbaren Wertebereichs bleibt.
5 & 6: Gleiche Vorzeichen der Summanden, mit Bereichsüberschreitung
Bei gleichen Vorzeichen der Summanden muß die Summe dasselbe Vorzeichen haben wie beide Summanden. Diese beiden Fälle sind Beispiele, bei denen eine Bereichsüberschreitung auftritt, weil die Summe außerhalb des darstellbaren Wertebereichs liegt, obwohl beide Summanden innerhalb liegen. Dieser auftretende Überlauf (engl. Overflow), der nicht mit dem Übertrag (engl. Carry) verwechselt werden darf, ist daran zu erkennen, daß 2 positive Summenden eine scheinbar negative Summe haben oder umgekehrt. Ein Addierer für Komplementrechnungen sollte einen solchen Überlauf als Statusbit automatisch erzeugen, weil das Ergebnis dann nicht mehr darstellbar und damit ungültig ist.

Für die anschließenden Rechnbeispiele werden zunächst die negativen Werte der drei gewählten Zahlen x = 270; y = 164 und z = 358 als 10-er-Komplemente in zwei Schritten gebildet:

neg. Wert (10-er-Komplement, 10K) = 9-er.Komplement (9K) + 1
        x = 270            y = 164            z = 358           positive Zahlen
            ---               -----              -----
       9K = 729           9K = 835           9K = 641           ziffernweise Ergänzung zu 9
          +   1              +   1              +   1
            ---                ---                ---
      - x = 730          - y = 836          - z = 642           negative Zahlen als
            ===                ===                ===           Komplementdarstellung

Auf welche Weise das 9-er-Komplement ohne Subtraktionsrechnung gebildet werden kann, wird am Ende dieses Abschnitts nach den Rechenbeispilen erläutert.

1 & 2: Verschiedene Vorzeichen der Sunmmanden
Überträge in die Tausenderstelle C = 103 (in Klammern) werden weggelassen (Addition modulo 1000), wodurch – C ohne Subtraktionsrechnung wegfällt. Eine negative Summe kann zum Überprüfen durch Komplementbildung in Vorzeichen und Betrag umgewandelt werden.

       x =   270         y =   164         s2 =   894
     - y =   836       - x =   730                ---
             ---               ---         9K =   105
      s1 =(1)106        s2 =   894            +     1
             ===               ===                ---
      Summe pos.        Summe neg.       - s2 =   106  = s1 (stimmt)
                                                  ====

3 & 4: Gleiche Vorzeichen der Sunmmanden ohne Bereichsüberschreitung

       x =   270       - x =   730         s4 =   566
     + y =   164       - y =   836                ---
             ---               ---         9K =   433
      s3 =   434        s4 =(1)566            +     1
             ===               ===                ---
      Summe pos.        Summe neg.       - s4 =   434 = s3 (stimmt)
                                                  ====

5 & 6: Gleiche Vorzeichen der Sunmmanden mit Bereichsüberschreitung
In diesen Fällen ist die Summe aus zwei positiven Summanden scheinbar negativ oder aus zwei negativen Summanden scheinbar positiv. Damit ist der Wertebereich für die Komplementdarstellung überschritten und die Summe nicht mehr darstellbar, also ungültig.

       x =   270                    - x =   730
     + z =   358                    - z =   642
             ---                            ---
      s5 =   628                     s6 =(1)372
             ===                            ===
      Summanden pos.                 Summanden neg.
      x, z < 500                     x, z ≥ 500
      Summe scheinbar neg.           Summe scheinbar pos.
      s5 ≥ 500 (ungültig!)           s6 < 500 (ungültig!)
      Bereichsüberschreitung!        Bereichsüberschreitung!

Normalerweise ist in Rechenmaschinen ein so großer Wertebereich realisiert, daß derartige Bereichsüberschreitungen nur in seltenen Sonderfällen auftreten. In den vorstehenden Rechenbeispielen ist das 10-er-Komplement jedes Mal explizit gebildet worden, um das Verfahren detailliert verständlich darzustellen. In der Rechentechnik wird diese '1' normalerweise gemeinsam mit dem 9-er-Komplement in einem Schritt addiert, indem sie über den ansonsten unbenutzten Übertragseingang c0 der niederwertigsten Addiererstelle eingespeist wird.

Erfahrungsgemäß treten beim Rechnen im Dezimalsystem und im Binärsystem verschiedene Ungenauigkeiten beim Runden auf. Das hat insbesondere bei kaufmännischen Berechnungen gestört, bei dem alle Beteiligten lediglich mit den bekannten Rundungsfehlern im Derimalsystem vertraut waren. Deshalb ist zu Beginn der Computerentwicklung immer wieder versucht worden, Maschinen zu entwickeln, die (ggf. indirekt) mit Dezimalzahlen rechnen. Wegen der tecnischen Vorteile von binär gespeicherten Zahlen sind in solchen Rechnern meistens binär codierte Dezimalziffern verwendet worden. Um die 10 verschiedenen Ziffern (0 – 9) des Dezimalsystems zu codieren, sind mindestens 4 Bit erforderlich, mit denen 16 verschiedene Kombinationen gebildet werden können. Damit bleiben 6 Kombinationen ungenutzt, die gewisse Freiheiten in der Codewahl ermöglichen. In Tabelle 2-3 ist eine Auswahl von drei derartigen Codes mit verschiedenen Eigenschaften istzusammengestellt.

 
Tabelle 2-3: Binär codierte Dezimalziffern

Dezimal-
ziffer
Dualer
Code
Aiken-
code
Stibitz-
code
0
1
2
3
4
0000
0001
0010
0011
0100
0000
0001
0010
0011
0100
0011
0100
0101
0110
0111
5
6
7
8
9
0101
0110
0111
1000
1011
1011
1100
1101
1110
1111
1000
1001
1010
1011
1100
Stellen-
werte
8421
eindeutig
2421
mehrdeutig
keine
 
Anmer-
kungen
einfache
Konvertierung
9-er Komplement
durch Invertierung
9-er Komplement
durch Invertierung

Die Ziffern im normalen Dualcode können zwar leicht konvertríert werden, bieten jedoch keine Vorteile, wenn statt der Subtraktion Komplemente addiert werden sollen. Das ist bei den anderen beiden Codes in Tabelle 2-3 ganz anders, die eine Symmetrieachse zwischen den Ziffern 4 und 5 haben. Dadurch ist das 9-er-Komplement leicht zu gebilden, indem entweder die 4 Bits einer Ziffer invertiert werden oder das 9-er-Komplement einfach an den inversen Ausgängen der Register-Flipflops abgegriffen wird, die seinerzeit meistens noch aus diskreten Bauteilen bestanden. Bei dem nach dem amerikanischen Computer-Pionier Howard H. Aiken (1900 – 1973) benannten Aiken-Code haben die Bits sogar einen festen Stellenwert (2 4 2 1). Im Gegensatz dazu hat der Stibitz-Code keine festen Stellenwerte. Er entsteht aus dem normalen Dualcode durch Addition einer 3 = (0011)2 und heißt deshalb auch 3-Exzess-Code. Wie aus Tabelle 2-3 ersichtlich, ergibt sich auch im Stibitz-Code das 9-er-Komplement durch invertieren der 4 Bits einer Ziffer. Man kann anhand der Werte in Tabelle 2-3 leicht nachprüfen, daß der Stibitz-Code durch Addieren einer 13 (1101)2 in den Dualcode umgerechnet werden kann, wobei der enstehende Übertrag in die 16-er-Stelle weggelassen wird (Addition modulo 16).

Nach Angaben im Internet wird der Aiken-Code auch heute noch in zahlreichen Geräten verwendet, in denen Dezimalziffern angezeigt werden, z.B. in Digitaluhren. In Computern werden intern jedoch nahezu ausschließlich Binärzahlen verschiedener Formate verwendet. Lediglich bei der Ein- und Ausgabe werden dort Dezimalzahlen verwendet, mit denen der Bernutzer vertraut ist. Die Wertebereiche der Zahlen sind in modernen Prozessoren so groß, daß die anfänglichen Rundungsprobleme in kommerziellen Programmen heute verschwindend gering geworden sind (siehe auch IEEE Standard 754).   [^ Inhalt]

 
b) Binärsystem

Die Komplementdarstellung im Binärsystem wird heute allgemein in nahezu allen Computern für ganze Zahlen (Integer) mit unterschiedlicher Stellenzahl verwendet. Der o.a. IEEE Standard 754 sieht folgende 3 Formate vor:

Word Integer: 16 Bit, Wertebereich – 215 bis + 215 – 1
Short Integer: 32 Bit, Wertebereich – 231 bis + 231 – 1
Long Integer: 64 Bit, Wetebereich – 263 bis + 263 – 1
 
Gelegentlich begegnet man außerhalb dieses Standards in älteren 8 Bit breiten Mikroprozessoren auch noch
Byte Integer: 8 Bit, Wertebereich – 27 bis + 27 – 1

32 oder 64 Bit sind Stellenzahlen, von denen die Rechenmaschinenpioniere nur träumen konnten, als es noch keine hochintegrierten Schaltungen gab. Die folgenden Rechenbeispiele sollen wegen der besseren Übersicht mit einem Bereich von n = 5 Binärstellen plausibel dargelegt werden.

B =   2             Binärsystem
n =   5             Binärstellen (als Beispiel gewählt)
C = Bn = 25 = 32 verschiedene Zahlen (00000 – 11111)2

Mit 5 Binärstellen sind 25 = 32 verschiedene Zahlen darstellbar. Für ausschließlich natürliche Zahlen (positive ganze Zahlen) sind das die Werte von 0 bis 31. Für die Komplementdarstellung wird dieser Wertebereich jedoch halbiert, um 16 positive Zahlen y von 0 bis 15 und 16 negative Zahlen – y von – 1 bis – 16 darzustellen, denen die entsprechenden Komplemente – y = Bn y von 31 bis 16 zugeordnet werden. In Tabelle 2-4 sind alle 16 Wertepaare der positiven und die negativen Zahlen (im 2-er-Komplement) aufgelistet. Außerdem sind die Zahlen als 1-er-Komplemenet angegeben, die im Binärsysten durch einfaches Invertierten positiven Zahlen gebildet werden. Das 2-er-Komplement ergibt sich daraus durch Addition einer '1'. Falls ein im 2-er-Komplement vorliegendes negatives Ergebnis interpretiert werden soll, läßt sie sich auf dieselbe Methode (Invertierung + 1) in eine positive Zahl umwandeln.

 
Tabelle 2-4: Komplementdarstellung im Binärsystem (n = 5)

Wert
neg.
2-er-
Kompl.
1-er
Kompl.
pos.
Zahl
Wert
pos.
+ 0 00000 11111 00000 + 0
– 1 11111 11110 00001 + 1
– 2 11110 11101 00010 + 2
– 3 11101 11100 00011 + 3
– 4 11100 11011 00100 + 4
– 5 11011 11010 00101 + 5
– 6 11010 11001 00110 + 6
– 7 11001 11000 00111 + 7
– 8 11000 10111 01000 + 8
– 9 10111 10110 01001 + 9
– 10 10110 10101 01010 + 10
– 11 10101 10100 01011 + 11
– 12 10100 10011 01100 + 12
– 13 10011 10010 01101 + 13
– 14 10010 10001 01110 + 14
– 15 10001 10000 01111 + 15
– 16 10000 01111    

Für die folgenden Rechenbeispiele mit Komplementen, werden die drei positiven Binärzahlen x = 01001 = (9)10; y = 00101 = (5)10 und z = 01100 = (12)10 gewählt. Damit können die in Tabelle 2-2 für das Dezimalsystem angegebenen sechs systematisch verschiedenen Fälle der vorzeichengerechten Addition in Komplementrechnung dargestellt werden. Die Grenzen der Bereichsüberschreitung ½ × Bn sind im Binärsystem jedoch nicht ½ × 103 = 500 wie in Tabelle 2-2, sondern für Binärzahlen mit n = 5 Stellen ½ × 25 = 25-1 = 24 = 16.

Für die anschließenden Rechenbeispiele werden zunächst die negativen Werte der drei gewählten Zahlen x = 01001; y = 00101 und z = 01100 als 2-er-Komplemente im zwei Schritten gebildet, neg. Wert (= 2-er-Komplement, 2K = Negation + 1)

               (9)dez             (5)dez            (12)dez
        x = 01001          y = 00101          z = 01100          positive Zahlen
            -----              -----              -----
      Neg = 10110        Neg = 11010        Neg = 10011          ziffernweise Negation
          +     1            +     1            +     1
            -----              -----              -----
      - x = 10111        - y = 11011        - z = 10100          negative Zahlen als
            =====              =====              =====          Komplementdarstellung

Es ist zu erkennen, daß die höchstwertige Stelle (Bit 4) das Vorzeichen angibt. Bei einer führenden 0 handelt es sich um eine positive Binärzahl, und bei einer führenden 1 um eine negative Binärzahl in Komplementdarstellung. Mit diesen 3 Zahlen werden die 6 verschiedenen Fälle der vorzeichengerechten Addition dargestellt.

1 & 2: Verschiedene Vorzeichen der Sunmmanden
Überträge in die 32-er-Stelle C = 25 (in Klammern) werden weggelassen (Addition modulo 32), wodurch – C ohne Subtraktionsrechnung wegfällt. Eine negative Summe kann zum Überprüfen durch Komplementbildung in Vorzeichen und Betrag umgewandelt werden.


       x =   01001         y =  00101         s2 = 11100
     - y =   11011       - x =  10111              -----
             -----              -----        Neg = 00011
      s1 =(1)00100        s2 =  11100            +     1
             =====              =====              -----
      Summe pos.          Summe neg.        - s2 = 00100  = s1 (stimmt)
      Dez: 9 - 5 = 4      - 5 - 9 = - 4            =====

3 & 4: Gleiche Vorzeichen der Sunmmanden ohne Bereichsüberschreitung

       x =  01001      - x =  10111           s4 =  10010
     + y =  00101      - y =  11011                 -----
            -----             -----          Neg =  01101
      s3 =  01110      s4 =(1)10010              +      1
            =====             =====                 -----
      Summe pos.        Summe neg.          - s4 =  01110 = s3 (stimmt)
      Dez: 9 + 5 = 14   - 9 - 5 = - 14              ======

5 & 6: Gleiche Vorzeichen der Sunmmanden mit Bereichsüberschreitung
In diesen Fällen ist die Summe aus zwei positiven Summanden scheinbar negativ oder aus zwei negativen Summanden scheinbar positiv. Damit ist der Wertebereich für die Komplementdarstellung überschritten (Überlauf bzw. Overflow), d.h. die Summe ist mit dieser Stellenzahl nicht mehr darstellbar, also ungültig.

       x =   01001                    - x =   10111
     + z =   01100                    - z =   10100
             -----                            -----
      s5 =   10101                     s6 =(1)01011
             =====                            =====
      Summanden pos.                   Summanden neg.
      x, z < 16 (Bit 4 = 0             x, z ≥ 16 Bit 4 = 1)
      Summe scheinbar neg.             Summe scheinbar pos.
      s5 ≥ 16 (Bit 4 = 1)              s6 < 16 (Bit 4 = 0)
      Bereichsüberschreitung!          Bereichsüberschreitung!
      Ergebnis nicht darstellbar       Ergebnis nicht darstellbar

Normalerweise ist in Rechenmaschinen ein so großer Wertebereich realisiert, daß derartige Bereichsüberschreitungen nur in seltenen Sonderfällen auftreten. Wie oben bereits erwähnt, sind im IEEE Standard 754) drei unterschiedliche Formate ganzer Zahlen festgelegt (Word Integer 16 Bit) Short Integer 32 Bit und Long Integer 64 Bit), deren negative Werte als 2-er-Komplemente angegeben werden. Diese Formate werden u.a. von allen modernen Mikroprozessortypen unterstützt. In den vorstehenden Rechenbeispielen ist das 2-er-Komplement jedes Mal explizit gebildet worden, um das Verfahren detailliert verständlich darzustellen. In der Rechentechnik wird diese '1' normalerweise gemeinsam mit dem 1-er-Komplement (negierte Zahl) in einem Schritt addiert, indem sie in den ansonsten unbenutzten Übertragseingang c0 der niederwertigsten Addiererstelle eingespeist wird.   [^ Inhalt]

 
3. Quellen

[1] H.Ch. Zeidler, M. Gärtner: Vorlesungsumdruck
Informatik für Ingenieure – Grundzüge der Datentechnik
Institut für Datenverarbeitungsanlagen, TU Braunschweig, 1992
[2] M. Gärtner: Übungskolleg
Informatik für Ingenieure – Grundzüge der Datentechnik
Institut für Datenverarbeitungsanlagen, TU Braunschweig, 1987 – 2002
[^ Inhalt]
Navigation: Home
Ing
Berufliches
Mathematisches
Polyadische Zahlensysteme
Logarithmen & Gleitkommazahlen
Toepler-Algorithmus
Sprachliches
Persönliches

Stand: 07.10.2020 / © MG