+4 Daumen
821 Aufrufe

Die schriftliche Addition von Binärzahlen bereitet keine Schwierigkeiten, wenn man weiß, dass I+I=I0 und dass hier bereits ein Übertrag fällig wird.

Die folgende Subtraktionsaufgabe

  I I 0 0
– I 0 I 0

kann auf eine Addition zurückgeführt werden. Hierzu ersetzen wir im Subtrahenden jede 0 durch eine I und jede I durch eine 0. Wir bilden also das Komplement des Subtrahenden und addieren dies:

  I I 0 0
+ 0 I 0 I
_ _ _ _ _
I 0 0 0 I

Die erste Ziffer Der Summe wird gestrichen und an der letzten Stelle addiert:

0 0 0 I 
  + I
_ _ _ _
0 0 I 0

Dann ist 0 0 I I die gesuchte Differenz, aber warum?

Wenn wir, statt eine vierstellige Binärzahl zu subtrahieren, ihr Komplement addieren, wird das Ergebnis gegenüber der gewünschte Differenz um I I I I zu groß. Diesen Fehler korrigieren wir, indem wir I0000 subtrahieren und I addieren (denn –I0000 + I = –I I I I). Entsprechendes gilt natürlich auch für jede andere Stellenzahl. Im Bereich der Binärzahlen ist dies genau die Art, in der Computer subtrahieren.

Die Aufgabe II00 ·I00I führen wir ebenfalls auf die Addition zurück, nachdem wir allerdings zuvor den ersten Faktor immer wieder halbiert und den zweiten Faktor gleichzeitig verdoppelt haben. Verdoppeln heißt, am Ende eine Null anfügen und Halbieren heißt streichen der letzten Ziffer. Wenn eine I gestrichen wird, entsteht ein Fehler, der gleich der simultan verdoppelten Zahl ist. Dann sieht die Rechnung so aus:

I I 0 0 · I 0   0 I 
I I 0 · I 0 0 I 0
    I I · I 0 0 I 0 0
      I · I 0 0 I 0 0 0

In den letzten beiden Zeilen wurde in der Spalte der Halbierungen eine I gestrichen. Dabei entsteht jeweils ein Fehler, der in der entsprechenden rechten Spalte der Verdopplungen zu finden ist. Folglich müssen wir diese beiden Zahlen noch addieren:

    I 0 0 I 0 0
+ I 0 0 I 0 0 0
_ _ _ _ _ _ _ _
I I 0 I I 0 0

Also gilt II00 · I00I = II0II00.

Mechanisch läuft dies Verfahren so ab, dass im zweiten Faktor immer wieder eine Null angefügt wird, während gleichzeitig im ersten Faktor immer wieder die letzte Ziffer weggelassen wird, bis nur noch eine I dasteht. Zum Schluss werden nur die Zahlen des zweiten Faktors addiert, bei denen der erste Faktor auf I endet.

Die Begründung für dies Verfahren erkennt man unmittelbar in der Notation als schriftliche Multiplikation. Im Falle binärer Multiplikation bietet das Verfahren des Verdoppelns und Halbierens keinen Vorteil gegenüber der schriftlichen Multiplikation. Es hat aber den Vorteil, dass es in jedem Zahlensystem anwendbar ist und sogar dann noch nützlich bleibt, wenn die Faktoren nicht Systemzahlen sind. Das Prinzip wurde schon im Papyrus Rhind der Babylonier genannt.

Die Grundrechenarten „–“ und „·“ wurden bereits auf die vier Rechenarten „+“, „Verdoppeln“, „Halbieren“ und „Komplementbildung“ zurückgeführt. Für die Division ist das ebenfalls möglich, aber mit etwas mehr Aufwand verbunden. Wir führen das Verfahren am Beispiel der Aufgabe I00000I:I0I vor. Darin heißt I00000I der Dividend und I0I der Divisor. Wir beginnen mit dem Zahlenpaar (Divisor, I) und verdoppeln beide Komponenten je so lange, wie in der Spalte des Divisors der gegebene Dividend nicht überschritten wird:

      I 0 I :       I
    I 0 I 0 :     I 0
I 0 I 0 0 :   I 0 0
I 0 I 0 0 0 : I 0 0 0


In der linken Spalte werden genau diejenigen Zahlen addiert, deren Summe I00000I (also den Dividend) ergibt. Zahlen, die als Summand nicht gebraucht werden, werden zusammen mit der ganzen Zeile gestrichen. Die nicht gestrichenen Zahlen werden in jeder Spalte addiert:

      I 0 I :         I
  I 0 I 0 :     I 0 Streichen
I 0 I 0 0 :   I 0 0
I 0 I 0 0 0 : I 0 0 0
_ _ _ _ _ _ _ _ _ _ _ _
I 0 0 0 0 0 I  I I 0 I

Dann ist die Summe II0I der rechten Spalte das Ergebnis der Aufgabe I00000I:I0I.

geschlossen: Wissensartikel
von Roland
Avatar von 123 k 🚀

Ich hänge immer noch beim ersten Beispiel: Die Subtraktion

  1100
– 1010
------
= 0010

wird durch das beschriebene Verfahren als Addition ausgeführt:

    1100
+ 0101
+ 1
--------
= 1'0010

Das Verfahren wird so beschrieben: "Wir bilden also das Komplement des Subtrahenden und addieren dies. Die erste Ziffer der Summe wird gestrichen und an der letzten Stelle addiert."  Müsste das Verfahren nicht ein wenig umformuliert werden? Ich bekomme aus irgendeinem Grund den Fall 1-0 damit nicht richtig berechnet.

  I-0 berechne ich als I+I=I0. Im Ergebnis streiche ich die erste (I) und addiere sie zu zur letzten (0): 0+I=I. Das Ergebnis ist richtig.

Entschuldige, das hatte ich falsch eingetippt. Ich hatte mich an 1-1=0 versucht. Daraus wird ja dann 1+0=1. Doch wie geht es dann weiter?

Das von mir geschilderte Verfahren eignet sich nur für Subtraktionen mit positivem Ergebnis. Andere Subtraktionen brauchen ein Vorzeichen-Bit. Darüber habe ich nicht reflektiert.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community