Zum Inhalt springen
Zurück zur Themenübersicht

Technische Informatik

Rechnen mit Dualzahlen: Addition, Subtraktion, Verschieben

Wie ein Prozessor mit einem einzigen Addierwerk alle vier Grundrechenarten bewältigt.

Benötigte Grundlagen

Dieses Vorwissen brauchst du für das Kapitel. Schau kurz nach, wenn dir etwas davon nicht mehr präsent ist, sonst leg direkt los.

Einführung

Ein Prozessor kennt keine Rechenregeln, wie du sie gelernt hast. Er kennt Bitmuster und ein Addierwerk.

Trotzdem rechnet er Subtraktionen, Multiplikationen und Divisionen. Die Frage ist, wie man alles auf Addieren zurückführt, und die Antwort ist bemerkenswert sparsam: Subtraktion wird zur Addition der Gegenzahl, Multiplikation mit Zweierpotenzen zum Verschieben.

Am Ende dieses Kapitels rechnest du wie ein Prozessor, und du erkennst, woran er einen bemerkt.

Das kannst du nach diesem Kapitel

  • schriftlich addieren und den Übertrag sicher führen.

  • Subtraktion als Addition des ausführen.

  • einen Überlauf an den Vorzeichen der Operanden und des Ergebnisses erkennen.

  • Multiplikation und Division mit Zweierpotenzen durch Verschieben ausführen.

  • begründen, warum ein einziges Addierwerk für alle Grundrechenarten genügt.

Kurz aufgefrischt

Vorausgesetzt werden , und Zahlbereich aus Zahlen im Rechner. Insbesondere: −x-x entsteht durch Umkehren aller und Addition von eins.

Addition im Dualsystem

Die schriftliche Addition funktioniert genau wie im Dezimalsystem, nur ist der Vorrat kleiner. Vier Fälle je Stelle:

aabbÜbertrag einSummeÜbertrag aus
00000
01010
11001
11111

Der Kern ist 1+1=1021 + 1 = 10_2: Man schreibt 0 und überträgt 1. Das ist dasselbe Prinzip wie 7+5=127 + 5 = 12 im Dezimalsystem, nur tritt es viel häufiger auf.

  1 1 1 1 1 1    ← Überträge
  0 1 0 1 1 0 1  (45)
+ 0 0 1 1 0 1 1  (27)
---------------
  1 0 0 1 0 0 0  (72)

Probe: 64+8=7264 + 8 = 72. Stimmt.

45 + 27 = 72

111111Ü0101101(45)+0011011(27)1001000(72)Sechs der sieben Stellenerzeugen einen Übertrag, dieZeile oben ist nicht Zierrat,sondern die halbe Rechnung.

Rechne die Spalten von rechts nach links mit und vergleiche jedes Mal mit der Übertragszeile oben. Der Kern ist 1+1=1021 + 1 = 10_2: Man schreibt 0 und überträgt 1, dasselbe Prinzip wie 7+5=127 + 5 = 12 im Dezimalsystem, nur tritt es viel häufiger auf, weil der Ziffernvorrat kleiner ist. In dieser Rechnung erzeugen sechs der sieben Stellen einen Übertrag, und einer davon läuft durch drei Stellen weiter. Genau deshalb steht die Übertragszeile ganz oben und nicht am Rand: Ohne sie kann man eine Spalte nicht abschließen, weil zu aa und bb noch ein drittes hinzukommt. Probe über die Dezimalwerte rechts: 45+27=7245 + 27 = 72, und 72=64+872 = 64 + 8 passt zu den beiden Einsen im Ergebnis.

Subtraktion ohne Subtrahierwerk

Nun der entscheidende Kunstgriff. Statt a−ba - b zu berechnen, rechnet der Prozessor

a−b=a+(−b)a - b = a + (-b)

und −b-b ist das von bb. Er braucht also keine eigene Subtraktionsschaltung, sondern nur einen Baustein, der umkehrt, und das vorhandene Addierwerk.

Beispiel 45−2745 - 27 bei 8 Bit:

27       = 0001 1011
umkehren = 1110 0100
  + 1    = 1110 0101   = -27

  0010 1101   ( 45)
+ 1110 0101   (-27)
-----------
1 0001 0010   ( 18)

Die neunte Stelle fällt weg, übrig bleibt 0001 00102=180001\,0010_2 = 18. Und 45−27=1845 - 27 = 18 stimmt.

🔴 Halte fest, warum das aufgeht: Das Wegfallen der überzähligen Stelle ist kein Fehler, den man in Kauf nimmt, sondern genau der Mechanismus. Bei nn Bit rechnet die Hardware ohnehin „modulo 2n2^n", und das Zweierkomplement ist so gebaut, dass diese Rechnung das richtige Ergebnis liefert.

45 − 27 als Addition von −27

11111Ü00101101(45)+11100101(−27)100010010(18)27 umgekehrt ergibt 1110 0100,plus eins ergibt 1110 0101.Das ist −27.

Der Prozessor subtrahiert nicht. Er rechnet a−ba - b als a+(−b)a + (-b), und −b-b ist das . Er braucht deshalb keine eigene Subtraktionsschaltung, sondern nur einen Baustein, der umkehrt, und das Addierwerk, das er ohnehin hat. Sieh dir an, was das Bild zeigt: Es ist dieselbe schriftliche Addition wie im Abschnitt davor, mit derselben Übertragszeile und denselben Regeln: nur die Bitmuster sind andere. Das Ergebnis 0001 00100001\,0010 ist 1818, und 45−27=1845 - 27 = 18 stimmt. Die überzählige neunte Stelle fällt heraus, und weil beide Summanden verschiedene Vorzeichen haben, kann dabei kein Überlauf entstehen.

Überlauf erkennen

Im vorigen Kapitel stand, dass ein nicht gemeldet wird. Erkennen lässt er sich trotzdem, und zwar an einer einfachen Regel:

Ein Überlauf liegt vor, wenn beide Summanden dasselbe Vorzeichen haben und das Ergebnis ein anderes.

Beispiele bei 8 :

  0111 1000  (120)
+ 0000 1111  ( 15)
-----------
  1000 0111  (-121)   ← positiv + positiv = negativ → Überlauf

  1000 0001  (-127)
+ 1111 1010  (  -6)
-----------
1 0111 1011  (123)    ← negativ + negativ = positiv → Überlauf

Warum genügt diese Regel? Weil zwei Zahlen mit verschiedenem Vorzeichen nie einen Überlauf erzeugen können: Ihre Summe liegt betragsmäßig zwischen den beiden, also erst recht im Bereich. Nur gleiche Vorzeichen können hinausführen, und dann kippt zwangsläufig das Vorzeichenbit.

Beachte, dass die weggefallene neunte Stelle kein verlässliches Anzeichen ist. Im ersten Beispiel gibt es keinen Übertrag aus der obersten Stelle und trotzdem einen Überlauf; im zweiten gibt es einen Übertrag und ebenfalls einen Überlauf. Der Übertrag zählt bei Zahlen ohne Vorzeichen, die Vorzeichenregel bei Zahlen mit Vorzeichen.

120 + 15 ergibt −121

1111Ü01111000(120)+00001111(15)10000111(−121)Überlauf: beide Summandenhaben dasselbe Vorzeichen, dasErgebnis ein anderes.Kein Übertrag fällt heraus,und trotzdem ist das Ergebnisfalsch. Der Übertrag ist nichtdas Anzeichen.

Zwei positive Zahlen, und heraus kommt eine negative: 120+15120 + 15 müsste 135135 sein, in acht passt aber nur bis 127127. Das Vorzeichenbit ist umgekippt, und der Rechner meldet das nicht von sich aus. Er rechnet einfach weiter. Erkennen lässt es sich an einer einfachen Regel: liegt vor, wenn beide Summanden dasselbe Vorzeichen haben und das Ergebnis ein anderes. Warum die Regel genügt: Zwei Zahlen mit verschiedenem Vorzeichen können nie hinausführen, denn ihre Summe liegt betragsmäßig zwischen den beiden. 🔴 Und beachte, was hier nicht passiert: Es fällt keine neunte Stelle heraus. Der Übertrag ist bei Zahlen mit Vorzeichen kein verlässliches Anzeichen. Er zählt nur bei Zahlen ohne Vorzeichen.

Multiplizieren durch Verschieben

Im Dezimalsystem hängt man beim Multiplizieren mit 10 eine Null an. Im gilt dasselbe mit 2:

0000 01012 (5)→links0000 10102 (10)0000\,0101_2\ (5) \quad \xrightarrow{\text{links}} \quad 0000\,1010_2\ (10)

Ein Schritt nach links verdoppelt, ein Schritt nach rechts halbiert. Um 2k2^k verschiebt man um kk Stellen.

Der Grund steckt im Stellenwert: Jede Stelle rückt auf die nächsthöhere Potenz, und jede Potenz ist doppelt so groß wie die vorige.

Damit lässt sich jede Multiplikation auf Verschieben und Addieren zurückführen, denn jeder Faktor ist eine Summe von Zweierpotenzen:

5⋅13=13⋅(4+1)=(13≪2)+13=52+13=655 \cdot 13 = 13 \cdot (4 + 1) = (13 \ll 2) + 13 = 52 + 13 = 65

Dabei bedeutet ≪2\ll 2 „um zwei Stellen nach links verschieben".

Genau so arbeiten einfache Multiplikationswerke: Sie gehen die des einen Faktors durch, verschieben den anderen entsprechend und addieren auf. Wieder genügt das eine Addierwerk.

Beim Verschieben nach rechts ist eine Feinheit zu beachten. Bei Zahlen ohne Vorzeichen schiebt man vorne Nullen nach. Bei Zahlen mit Vorzeichen muss das Vorzeichenbit erhalten bleiben, sonst würde aus einer negativen Zahl plötzlich eine positive; man schiebt deshalb vorne das Vorzeichenbit nach. Und die Division durch Verschieben rundet immer ab, weshalb −7≫1-7 \gg 1 nicht −3-3, sondern −4-4 ergibt.

Verschieben ist Multiplizieren

AusdruckBitmusterWert50000 010155 ≪ 10000 1010105 ≪ 20001 010020Ein Schritt nach links verdoppelt,ein Schritt nach rechts halbiert.Um 2^k verschiebt man um k Stellen.

Vergleiche die drei Bitmuster: Es ist immer dieselbe Folge 101101, sie rückt nur jedes Mal um eine Stelle nach links, und der Wert verdoppelt sich. Der Grund steckt im Stellenwert: Jede Stelle rückt auf die nächsthöhere Zweierpotenz, und jede Potenz ist doppelt so groß wie die vorige. Im Dezimalsystem machst du dasselbe, wenn du beim Multiplizieren mit 10 eine Null anhängst. Damit lässt sich jede Multiplikation auf Verschieben und Addieren zurückführen, denn jeder Faktor ist eine Summe von Zweierpotenzen: 5⋅13=13⋅(4+1)=(13≪2)+13=52+13=655 \cdot 13 = 13 \cdot (4 + 1) = (13 \ll 2) + 13 = 52 + 13 = 65. Genau so arbeiten einfache Multiplikationswerke, und wieder genügt ihnen das eine Addierwerk.

Warum ein Addierwerk genügt

Fasse zusammen, was der Prozessor wirklich braucht:

RechenartRückführung
AdditionAddierwerk
Subtraktiona+(−b)a + (-b), also umkehren, eins addieren, addieren
Multiplikationwiederholtes Verschieben und Addieren
Divisionwiederholtes Verschieben und Subtrahieren

Alle vier Grundrechenarten laufen auf Addieren und Verschieben hinaus. Das ist der Grund, warum ein Rechenwerk mit vergleichsweise wenigen Bauteilen auskommt, und es erklärt, warum das sich durchgesetzt hat: Es macht die Subtraktion zur Addition.

Wie ein Addierwerk aus entsteht, ist Gegenstand des Kapitels Vom Halbaddierer zum von-Neumann-Rechner.

Subtraktion über das Zweierkomplement

Berechne 38−5338 - 53 mit 8-Bit-Zweierkomplement und deute das Ergebnis.

  1. 1

    Schritt 1: beide Zahlen dual: 38=0010 0110238 = 0010\,0110_2 und 53=0011 0101253 = 0011\,0101_2.

  2. 2

    Schritt 2: von 53:

    53       = 0011 0101
umkehren = 1100 1010
  + 1    = 1100 1011   = -53
  3. 3

    Schritt 3: addieren:

      0010 0110   ( 38)
+ 1100 1011   (-53)
-----------
  1111 0001

    Hier fällt keine neunte Stelle an.

  4. 4

    Schritt 4: Ergebnis deuten: Das vorderste ist 1, die Zahl ist also negativ. Betrag über die Rückrichtung: umkehren ergibt 0000 11100000\,1110, plus eins ergibt 0000 1111=150000\,1111 = 15.

  5. 5

    Ergebnis: −15-15. Und 38−53=−1538 - 53 = -15 stimmt.

  6. 6

    Überlaufprüfung: Die Summanden haben verschiedene Vorzeichen (positiv und negativ), also kann kein Überlauf vorliegen. Man muss gar nicht weiter prüfen.

0010 0110+1100 1011=1111 0001=−150010\,0110 + 1100\,1011 = 1111\,0001 = -15. Kein Überlauf, weil die Vorzeichen verschieden sind.

Multiplizieren durch Verschieben und Addieren

Berechne 13⋅513 \cdot 5 nur mit Verschiebungen und Additionen.

  1. 1

    Schritt 1: den Faktor 5 in Zweierpotenzen zerlegen: 5=4+1=22+205 = 4 + 1 = 2^2 + 2^0. Dual ist das 1012101_2, und die gesetzten stehen genau an den Stellen 2 und 0.

  2. 2

    Schritt 2: für jedes gesetzte Bit verschieben: 13⋅22=13≪213 \cdot 2^2 = 13 \ll 2 und 13⋅20=1313 \cdot 2^0 = 13.

  3. 3

    Schritt 3: Verschiebung ausführen:

    13      = 0000 1101
13 << 1 = 0001 1010   (26)
13 << 2 = 0011 0100   (52)
  4. 4

    Schritt 4: addieren:

      0011 0100   (52)
+ 0000 1101   (13)
-----------
  0100 0001   (65)
  5. 5

    Probe: 13⋅5=6513 \cdot 5 = 65. Stimmt.

  6. 6

    Das Muster dahinter: Man geht die Bits des einen Faktors von rechts nach links durch. Ist das Bit 1, addiert man den anderen Faktor in der aktuellen Verschiebung; ist es 0, überspringt man. Genau so arbeitet ein einfaches Multiplikationswerk, und es kommt dabei mit einem Addierwerk und einem Schieberegister aus.

13⋅5=(13≪2)+13=52+13=6513 \cdot 5 = (13 \ll 2) + 13 = 52 + 13 = 65, ausgeführt mit einer Verschiebung und einer Addition.

Typischer Fehler

„Wenn beim Addieren ein Übertrag über die letzte Stelle hinausgeht, ist das ein ."

Das gilt für Zahlen ohne Vorzeichen, aber nicht für das Zweierkomplement, und die Verwechslung führt zu falschen Ergebnissen in beide Richtungen.

Fall 1: Übertrag, aber kein Überlauf. Rechne 45+(−27)45 + (-27):

  0010 1101   ( 45)
+ 1110 0101   (-27)
-----------
1 0001 0010   ( 18)

Die neunte Stelle fällt weg, das Ergebnis 18 ist völlig richtig. Der Übertrag gehört hier zum Verfahren.

Fall 2: kein Übertrag, aber Überlauf. Rechne 120+15120 + 15:

  0111 1000   (120)
+ 0000 1111   ( 15)
-----------
  1000 0111   (-121)

Kein Übertrag über die achte Stelle hinaus, und das Ergebnis ist trotzdem falsch.

Die beiden Fälle zeigen, dass der Übertrag hier gar nichts aussagt. Zuständig ist die Vorzeichenregel: gleiche Vorzeichen bei den Summanden, anderes Vorzeichen beim Ergebnis.

Prozessoren führen deshalb zwei getrennte Anzeigen mit, ein Übertragsbit für vorzeichenlose und ein Überlaufbit für vorzeichenbehaftete Rechnung. Welches gilt, entscheidet der im Programm, nicht die Hardware.

Übung 1

leicht

a) Addiere dual: 0011 01102+0001 110120011\,0110_2 + 0001\,1101_2. Probe im Dezimalsystem. b) Was ergibt 0000 01102≪30000\,0110_2 \ll 3? Welcher Rechnung entspricht das? c) Was ergibt 0011 00002≫20011\,0000_2 \gg 2?

Tipp anzeigen

Zu a): Schreibe die Überträge über die Spalten.

Lösung anzeigen

a)

    1 1 1 1
  0011 0110   (54)
+ 0001 1101   (29)
-----------
  0101 0011   (83)

Probe: 54+29=8354 + 29 = 83, und 64+16+2+1=8364 + 16 + 2 + 1 = 83. Stimmt.

b) 0000 01102=60000\,0110_2 = 6. Drei Stellen nach links: 0011 00002=480011\,0000_2 = 48. Das entspricht 6⋅23=6⋅8=486 \cdot 2^3 = 6 \cdot 8 = 48.

c) 0011 00002=480011\,0000_2 = 48. Zwei Stellen nach rechts: 0000 11002=120000\,1100_2 = 12. Das entspricht 48:4=1248 : 4 = 12.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Dual addieren: dieselbe schriftliche Addition, nur mit Übertrag bei 2

    Man addiert spaltenweise von rechts wie im Dezimalsystem, nur entsteht der Übertrag schon bei 2 statt bei 10, denn zwei ist im bereits „eine Stelle weiter“. 0011 01102+0001 11012=0101 001120011\,0110_2 + 0001\,1101_2 = 0101\,0011_2.

    54+29=8354 + 29 = 83; 0101 00112=64+16+2+1=830101\,0011_2 = 64+16+2+1 = 83 ✓

    Zwischenergebnis

    0101 00112=830101\,0011_2 = 83

  2. 2

    b) Linksschieben ist Multiplizieren mit einer Zweierpotenz

    0000 01102=60000\,0110_2 = 6. Drei Stellen nach links ergibt 0011 00002=480011\,0000_2 = 48, und das entspricht 6⋅23=6⋅8=486 \cdot 2^3 = 6 \cdot 8 = 48. Jede Verschiebung um eine Stelle nach links verdoppelt den Wert.

    6⋅23=486 \cdot 2^3 = 48

    Zwischenergebnis

    0011 00002=480011\,0000_2 = 48

  3. 3

    c) Rechtsschieben ist Teilen durch eine Zweierpotenz

    0011 00002=480011\,0000_2 = 48. Zwei Stellen nach rechts ergibt 0000 11002=120000\,1100_2 = 12, also 48:22=48:4=1248 : 2^2 = 48 : 4 = 12. Jede Verschiebung nach rechts halbiert.

    48:22=1248 : 2^2 = 12

    Zwischenergebnis

    0000 11002=120000\,1100_2 = 12

Übung 2

mittel

Rechne alles mit 8-Bit-Zweierkomplement.

a) Berechne 70−2570 - 25 über das . b) Berechne 100+45100 + 45 und beurteile das Ergebnis. c) Berechne −70+(−70)-70 + (-70) und beurteile das Ergebnis. d) Erkläre, warum verschiedene Vorzeichen nie zu einem Überlauf führen können.

Tipp anzeigen

Zu b) und c): Schreibe zuerst den Bereich −128…127-128 \ldots 127 hin.

Lösung anzeigen

a) 25=0001 100125 = 0001\,1001, umgekehrt 1110 01101110\,0110, plus eins 1110 0111=−251110\,0111 = -25.

  0100 0110   ( 70)
+ 1110 0111   (-25)
-----------
1 0010 1101   ( 45)

Neunte Stelle fällt weg, Ergebnis 0010 11012=450010\,1101_2 = 45. Richtig, und wegen verschiedener Vorzeichen kein Überlauf.

b) 100=0110 0100100 = 0110\,0100, 45=0010 110145 = 0010\,1101.

  0110 0100   (100)
+ 0010 1101   ( 45)
-----------
  1001 0001   (-111)

Beide Summanden positiv, Ergebnis negativ → Überlauf. Richtig wäre 145, was außerhalb von −128…127-128 \ldots 127 liegt. Das Register zeigt −128+16+1=−111-128 + 16 + 1 = -111.

c) −70=1011 1010-70 = 1011\,1010 (denn 70=0100 011070 = 0100\,0110, umgekehrt 1011 10011011\,1001, plus eins 1011 10101011\,1010).

  1011 1010   (-70)
+ 1011 1010   (-70)
-----------
1 0111 0100   (116)

Beide Summanden negativ, Ergebnis positiv → Überlauf. Richtig wäre −140-140, ebenfalls außerhalb des Bereichs.

d) Seien a>0a > 0 und b<0b < 0. Dann liegt a+ba + b betragsmäßig zwischen bb und aa, genauer gilt b<a+b<ab < a + b < a. Da beide Summanden im darstellbaren Bereich liegen, liegt jeder Wert dazwischen erst recht darin. Ein Überlauf ist damit ausgeschlossen. Anschaulich: Gegensätzliche Vorzeichen ziehen das Ergebnis zur Null hin, und zur Null hin verlässt man den Bereich nie.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Teil a): Komplement bilden, dann addieren

    Man bildet das Zweierkomplement des Subtrahenden und addiert es. Der Subtrahend ist die Zahl, die abgezogen wird, hier also 25.

    25 = 0001,1001 ;\to; 1110,0110 ;\to; 1110,0111

    Zwischenergebnis

    −25=1110 01112-25 = 1110\,0111_2.

    Verwechsle nicht, von welcher Zahl du das Komplement bildest. 70−2570 - 25 heißt 70+(−25)70 + (-25), nicht 25+(−70)25 + (-70).

  2. 2

    Teil b): Erst den Bereich, dann das Vorzeichen prüfen

    Man schreibt den Bereich −128…127-128 \ldots 127 hin, sieht dass 145 nicht hineinpasst, und bestätigt es an der Vorzeichenregel: positiv plus positiv ergibt negativ.

    0110,0100 + 0010,1101 = 1001,0001

    Zwischenergebnis

    Überlauf; das Register zeigt −111-111.

  3. 3

    Teil c): Derselbe Test in die andere Richtung

    Auch hier zuerst der Bereich: −140-140 liegt unterhalb von −128-128. Die Vorzeichenregel bestätigt es, diesmal mit negativ plus negativ ergibt positiv.

    1011,1010 + 1011,1010 = 1,0111,0100

    Zwischenergebnis

    Überlauf; das Register zeigt 116116.

    Beachte, dass hier ein Übertrag über die achte Stelle hinausgeht und ein Überlauf vorliegt, während in b) kein Übertrag anfiel und trotzdem ein Überlauf vorlag. Der Übertrag ist also kein Anzeichen.

  4. 4

    Teil d): Die Begründung sauber führen

    Man zeigt nicht an Beispielen, sondern allgemein: Bei a>0a > 0 und b<0b < 0 gilt b<a+b<ab < a+b < a. Die Summe liegt also zwischen zwei darstellbaren Werten und ist damit selbst darstellbar.

    b < a + b < a

    Zwischenergebnis

    Überlauf ausgeschlossen.

Übung 3

schwer

a) Berechne 11⋅611 \cdot 6 nur durch Verschieben und Addieren. Gib die einzelnen Schritte an. b) Begründe, warum ein Prozessor mit einem einzigen Addierwerk alle vier Grundrechenarten ausführen kann. c) Ein Programmierer ersetzt x : 8\texttt{x : 8} durch x >> 3\texttt{x >> 3}, um Zeit zu sparen. Bei welchen Werten von x\texttt{x} liefert das ein anderes Ergebnis als die Division? d) Ein 16-Bit-Zähler wird jede Sekunde um eins erhöht und ist vorzeichenbehaftet. Nach welcher Zeit tritt der erste auf?

Tipp anzeigen

Zu c): Denke an negative Zahlen und an das Abrunden.

Lösung anzeigen

a) 6=4+2=22+216 = 4 + 2 = 2^2 + 2^1, dual 1102110_2. Gesetzte an den Stellen 2 und 1.

11        = 0000 1011   (11)
11 << 1   = 0001 0110   (22)
11 << 2   = 0010 1100   (44)

  0010 1100   (44)
+ 0001 0110   (22)
-----------
  0100 0010   (66)

Also 11⋅6=(11≪2)+(11≪1)=44+22=6611 \cdot 6 = (11 \ll 2) + (11 \ll 1) = 44 + 22 = 66. Beachte, dass Bit 0 in 1102110_2 nicht gesetzt ist, deshalb wird 11 selbst nicht addiert.

b) Weil sich alle vier auf Addieren und Verschieben zurückführen lassen: Addition direkt. Subtraktion als a+(−b)a + (-b), wobei −b-b durch Bitumkehr und Addition von eins entsteht; nötig ist also nur ein Inverter zusätzlich. Multiplikation als wiederholtes Verschieben und Addieren entlang der Bits des einen Faktors. Division als wiederholtes Verschieben und Subtrahieren, was seinerseits Addition ist.

Der eigentliche Grund dahinter ist das Zweierkomplement. Es macht die Subtraktion zur Addition, und damit fällt die einzige Rechenart weg, die eine eigene Schaltung gebraucht hätte.

c) Bei negativen Werten von x\texttt{x}, die nicht durch 8 teilbar sind. Das arithmetische Rechtsschieben rundet immer ab, also in Richtung minus unendlich; die Ganzzahldivision rundet in den meisten Programmiersprachen dagegen in Richtung null.

Beispiel: −9≫3-9 \gg 3 ergibt −2-2, denn −9:8=−1,125-9 : 8 = -1{,}125 und abgerundet ist das −2-2. Die Division −9:8-9 : 8 liefert dagegen −1-1.

Bei nichtnegativen Werten und bei glatt teilbaren negativen Werten stimmen beide überein. Der Zeitgewinn ist auf heutigen Prozessoren ohnehin gering, weil Übersetzer solche Divisionen selbst in Verschiebungen umwandeln, wenn es zulässig ist. Die Ersetzung von Hand bringt also kaum Vorteile und schafft eine Fehlerquelle.

d) Bei 16 Bit mit Vorzeichen reicht der Bereich bis +32 767+32\,767. Der Überlauf tritt beim Schritt von 32 76732\,767 auf 32 76832\,768 ein, also nach 32 76832\,768 Sekunden ab dem Wert null.

32 768 s=546,13 min≈9,1 Stunden32\,768\ \text{s} = 546{,}13\ \text{min} \approx 9{,}1\ \text{Stunden}

Danach zeigt der Zähler −32 768-32\,768 und läuft von dort weiter hoch. Solche Fehler zeigen sich also erst nach Stunden Dauerbetrieb und werden bei kurzen Tests zuverlässig übersehen. Abhilfe: einen größeren Typ wählen, etwa 32 oder 64 Bit, oder den Zähler in geeigneten Abständen zurücksetzen.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Den Faktor in Zweierpotenzen zerlegen und verschoben addieren

    6=4+2=22+216 = 4 + 2 = 2^2 + 2^1, dual 1102110_2, gesetzte Bits an den Stellen 2 und 1. Also ist 11⋅6=(11≪2)+(11≪1)=44+22=6611 \cdot 6 = (11 \ll 2) + (11 \ll 1) = 44 + 22 = 66. Beachte: Bit 0 ist in 1102110_2 nicht gesetzt, deshalb wird 11 selbst nicht addiert.

    11⋅6=(11≪2)+(11≪1)=44+22=6611 \cdot 6 = (11 \ll 2) + (11 \ll 1) = 44 + 22 = 66

    Zwischenergebnis

    0100 00102=660100\,0010_2 = 66

  2. 2

    b) Warum ein Addierwerk für alle vier Grundrechenarten genügt

    Weil sich alle vier auf Addieren und Verschieben zurückführen lassen. Addition direkt. Subtraktion als a+(−b)a + (-b), wobei −b-b durch Bitumkehr und Addition von eins entsteht. Multiplikation als wiederholtes Verschieben und Addieren (Teil a). Division als wiederholtes Verschieben und Subtrahieren, was seinerseits Addition ist.

  3. 3

    c) Wo x >> 3 und x : 8 auseinanderlaufen

    Bei negativen Werten, die nicht durch 8 teilbar sind. Das arithmetische Rechtsschieben rundet immer ab, also in Richtung minus unendlich; die Ganzzahldivision rundet in den meisten Sprachen dagegen in Richtung null. Beispiel: −9≫3-9 \gg 3 ergibt −2-2 (denn −9:8=−1,125-9 : 8 = -1{,}125, abgerundet −2-2), die Division −9:8-9 : 8 dagegen −1-1.

    −9≫3=−2-9 \gg 3 = -2, aber −9:8=−1-9 : 8 = -1

  4. 4

    d) Wann ein 16-Bit-Zähler überläuft

    Bei 16 Bit mit Vorzeichen reicht der Bereich bis +32 767+32\,767. Der Überlauf tritt beim Schritt von 32 76732\,767 auf 32 76832\,768 ein, also nach 32 768 Sekunden ab dem Wert null. Das sind 546,13546{,}13 Minuten, rund 9,1 Stunden. Danach zeigt der Zähler −32 768-32\,768 und läuft von dort weiter hoch.

    32 768 s=546,13 min≈9,1 h32\,768\ \text{s} = 546{,}13\ \text{min} \approx 9{,}1\ \text{h}

    Zwischenergebnis

    Rund 9,1 Stunden.

Zusammenfassung

Die Dualaddition folgt demselben Schema wie die schriftliche Addition im Dezimalsystem, nur tritt der Übertrag wegen 1+1=1021+1 = 10_2 deutlich häufiger auf. Subtrahiert wird nicht, sondern der Prozessor rechnet a+(−b)a + (-b) mit dem ; die über die Wortbreite hinausgehende Stelle fällt dabei planmäßig weg, weil die Hardware ohnehin modulo 2n2^n arbeitet. Einen Überlauf erkennt man bei vorzeichenbehafteten Zahlen daran, dass beide Summanden dasselbe und das Ergebnis ein anderes Vorzeichen hat; der Übertrag aus der obersten Stelle ist dafür kein Anzeichen, denn er gehört zur vorzeichenlosen Rechnung. Verschiedene Vorzeichen können nie überlaufen, weil die Summe dann betragsmäßig zwischen den Summanden liegt. Multiplikation und Division mit Zweierpotenzen führt man durch Verschieben aus, links verdoppelt und rechts halbiert mit Abrundung, und jede beliebige Multiplikation lässt sich als Folge von Verschiebungen und Additionen entlang der gesetzten schreiben. Damit genügt dem Rechenwerk ein einziges Addierwerk für alle vier Grundrechenarten.