Dualsystem/Grundrechenarten

Grundrechenarten im Dualsystem

Analog zu den Zahlen im Dezimalsystem lassen sich mit Dualzahlen die gängigen arithmetischen Grundoperationen Addition, Subtraktion, Multiplikation und Division durchführen. Tatsächlich werden die benötigten Algorithmen sogar einfacher und lassen sich effizient mit logischen Schaltungen elektronisch realisieren. Die Einführung von Dualzahlen in der Rechentechnik brachte daher viele Vorteile.

Addition Beispiel 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0, Übertrag (carry) 1 ${{\begin{matrix}&1011_{2}\\\operatorname {+} &\ \ \ 11_{2}\\\end{matrix}} \over {\begin{matrix}&\ \ 1110_{2}\\\end{matrix}}}$	Subtraktion Beispiel 0 − 0 = 0 0 − 1 = 1, Übertrag (borrow) 1 1 − 0 = 1 1 − 1 = 0 ${\begin{matrix}&1011_{2}\\{-\ }&\ \ 111_{2}\\\end{matrix}} \over {\begin{matrix}&\ \ \ \ \ 100_{2}\end{matrix}}$
Multiplikation Beispiel 0 $\cdot$ 0 = 0 0 $\cdot$ 1 = 0 1 $\cdot$ 0 = 0 1 $\cdot$ 1 = 1 $1010_{2}{\cdot }11_{2}=11110_{2}$	Division Beispiel 0 / 0 = n.def. 0 / 1 = 0 1 / 0 = n.def. 1 / 1 = 1 $1010_{2}{/}10_{2}=101_{2}$

Schriftliche Addition

A	B	M1	M2	E
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
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

Die binäre Addition ist eine grundlegende Basisoperation in der Computerwelt. Will man zwei nicht negative Binärzahlen $A$ und $B$ addieren, kann man das wie im Dezimalsystem tun. Nur muss man beachten, dass beim Ergebnis an der jeweiligen Stelle keine „Zwei“ notiert wird, sondern eine Null und an die nächste Stelle ein Übertrag. Das geschieht analog zur Dezimaladdition, wenn sich bei der Addition einer Stelle eine Zehn ergibt:

Die Zahlen werden übereinander aufgeschrieben. Nun arbeitet man von rechts nach links alle Binärziffern (=Bits) von $A$ und $B$ simultan ab und erzeugt in jedem Zwischenschritt ein Ergebnisbit sowie ein Merkerbit (auch Übertrag genannt). Dabei werden die Bits entsprechend der Tabelle rechts zusammengezählt. In den Spalten A und B sind die Bits der zu addierenden Zahlen zu finden. In der Spalte $M_{1}$ steht das Merkerbit des vorherigen Zwischenschrittes. Daraus ergeben sich (entsprechend dieser Tabelle, welche einem Volladdierer entspricht) ein Ergebnisbit (E) und ein neues Merkerbit ($M_{2}$). Alle Ergebnisbits, von rechts nach links aneinandergereiht, stellen das Resultat dar. Entsteht beim letzten Zwischenschritt ein Merkerbit, so bekommt das Resultat links eine zusätzliche 1.

Am besten sieht man das anhand eines Beispiels. Hier werden die Zahlen A und B zusammengezählt. In jedem Schritt wird ein anfallendes Merkerbit bei der nächsten Ziffer notiert.

A = 10011010 (154)
B = 00110110 ( 54)
Merker = 01111100
————————
Ergebnis = 11010000 (208)
‗‗‗‗‗‗‗‗

Schriftliche Subtraktion

Die Subtraktion verhält sich analog zur Addition.

$0-0=0$

$0-1=1$, Übertrag (borrow) 1

$1-0=1$

$1-1=0$

Zwei Zahlen im Dualsystem können voneinander wie im folgenden Beispiel dargestellt subtrahiert werden:

${\begin{matrix}&1&1&0&1&1&1&0\\-&&&1&0&1&1&1\\&&{}_{1}&&{}_{1}&{}_{1}&{}_{1}&\end{matrix}} \over {\begin{matrix}=&1&0&1&0&1&1&1\end{matrix}}$

Hier wird die Subtraktion   110−23 = 87   durchgeführt. Die kleinen Einsen in der dritten Reihe zeigen den Übertrag. Das Verfahren ist das Gleiche, wie es in der Schule für das Dezimalsystem unterrichtet wird. Etwas ungewohnt sieht der Fall 0−1 aus. Zur Verdeutlichung das Beispiel 2−9 im Dezimalsystem: Man denkt sich eine Zehnerstelle vor die Zwei, wodurch sich die Subtraktion 12−9 ergibt. Die gedachte Zehnerstelle wird dann als Übertrag an die nächste Stelle weitergereicht. Im Dualsystem geschieht das Gleiche: Aus 0−1 wird 10−1. Als Ergebnis kann also eine 1 hingeschrieben werden; die vor die 0 gedachte Eins muss dann als Übertrag an die nächste Stelle geschrieben und von dieser zusätzlich abgezogen werden.

Das Verfahren funktioniert (wie auch im Dezimalsystem) nicht, wenn der Minuend (1. Zahl) kleiner ist als der Subtrahend (2. Zahl). Sollte das der Fall sein, erfolgt die Subtraktion einer Zahl durch die Addition des Zweierkomplementes dieser Zahl. Die Subtraktion einer positiven Zahl ergibt nämlich das gleiche Ergebnis wie die Addition der entsprechenden negativen Zahl mit dem gleichen Betrag:

${\begin{array}{crcccccccc|l|cr}&&0&1&1&1&0&1&1&0&{\text{Minuend}}&&118_{10}\\-&&1&0&0&1&1&0&0&1&{\text{Subtrahend}}&-&153_{10}\\\hline &&0&1&1&1&0&1&1&0&{\text{Minuend}}&&118_{10}\\+&(-)&0&1&1&0&0&1&1&1&{\text{Subtrahend (Zweierkomplement)}}&+&(-)153_{10}\\&{\color {blue}{}_{0}}&{}_{1}&{}_{1}&&&{}_{1}&{}_{1}&&&\\\hline =&&1&1&0&1&1&1&0&1&{\text{Ergebnis (Zweierkomplement, negativ)}}&=&-35_{10}\\\hline \hline &&0&0&1&0&0&0&1&1&{\text{Betrag des Ergebnisses}}&&35_{10}\\\end{array}}$

Wäre der (blau markierte) Übertrag 1, müsste das Zweierkomplement des Ergebnisses nicht mehr gebildet werden, da die vorzeichenlose Darstellung der positiven Zahlen im Zweierkomplement gleich ist (siehe Tabelle dort). Der Übertrag wird zu den (nicht dargestellten) führenden Einsen des Zweierkomplementes addiert, wodurch im Ergebnis nur führende Nullen entstehen. Als Beispiel dient die obige Rechnung 110−23 = 87  :

${\begin{array}{crccccccc|l}&&1&1&0&1&1&1&0&{\text{Minuend}}\\+&(-)&1&1&0&1&0&0&1&{\text{Subtrahend (Zweierkomplement)}}\\&{\color {blue}{}_{1}}&{}_{1}&&{}_{1}&&&&&\\\hline =&&1&0&1&0&1&1&1&\end{array}}$

Schriftliche Multiplikation

Die Multiplikation wird im Dualsystem genauso durchgeführt wie im Dezimalsystem. Dadurch, dass nur 0 und 1 als Ziffern vorkommen, ist die schriftliche Multiplikation jedoch sogar einfacher. Das folgende Beispiel, in dem die Zahlen 1100 (12) und 1101 (13) multipliziert werden, zeigt die Vorgehensweise.

Zuerst schreibt man die Aufgabenstellung in eine Zeile und zieht zur Vereinfachung einen Strich darunter.

1100 · 1101
———————————

Die erste Ziffer des zweiten Faktors ist eine Eins und deshalb schreibt man den ersten Faktor rechtsbündig unter diese Eins.

1100 · 1101
———————————
1100

Auch für alle weiteren Einsen des zweiten Faktors schreibt man den ersten Faktor rechtsbündig darunter.

1100 · 1101
———————————
1100
1100
0000
1100

Die so gewonnenen Zahlen zählt man dann zum Ergebnis der Multiplikation zusammen.

1100 · 1101
———————————
1100
+ 1100
+ 0000
+ 1100
———————————
10011100 (156)

Ein besonders einfacher Fall ist die Multiplikation einer positiven Dualzahl mit der Zahl 10 (2). In diesem Fall muss lediglich an die positive Dualzahl eine 0 angehängt werden:

$1101\cdot 10=11010$

$11010\cdot 10=110100$

usw.

Für diese Rechenoperation existieren einfache Befehle in der Digitaltechnik.

Bei der Multiplikation zweier Zweierkomplement-Dualzahlen wird der Booth-Algorithmus benutzt.

Schriftliche Division

Bei der Division zweier Dualzahlen werden folgende Algorithmen verwendet.

Am Beispiel der Division von 1000010 / 11 (entspricht 66:3 im Dezimalsystem)

1000010 ÷ 11 = 010110 Rest 0 (= 22 im Dezimalsystem) somit mod
− 011
—————
00100
− 011
————
0011
− 011
—————
0

Die Anwendung der Modulo-Funktion mit dem Divisor 10 (2) auf positive Dualzahlen ergibt immer 1, wenn die letzte Ziffer des Dividenden 1 ist und 0, wenn die letzte Ziffer des Dividenden 0 ist:

$1101\mod 10=1$

$1100\mod 10=0$

Für diese Rechenoperation, die einer UND-Verknüpfung mit 1 entspricht, existieren einfache Befehle in der Digitaltechnik.

Ein besonders einfacher Fall ist die Division mit Rest einer positiven Dualzahl durch die Zahl 10 (2). In diesem Fall muss lediglich die letzte Ziffer des Dividenden gestrichen werden. Ist die letzte Ziffer des Dividenden eine 1, so verschwindet dieser Rest. Entspricht bei diesem Verfahren die Anzahl der Divisionen durch 2 der Anzahl der Stellen des Dividenden, so ist das Endergebnis immer 0:

$1101\div 10=110$

$110\div 10=11$

$11\div 10=1$

$1\div 10=0$

Für diese Rechenoperation existieren einfache Befehle in der Digitaltechnik.