Wie Gatter Zahlen addieren

Ein XOR- und ein AND-Gatter reichen, um zwei Bits zu addieren. Häng vier Volladdierer hintereinander, und du kannst zwei beliebige Zahlen von 0 bis 15 addieren.

Probier das, bevor du weiterliest. Addiere 0101 und 0011 auf Papier im Binärsystem, so wie du dezimal addierst, und schreib jeden Übertrag über die nächste Spalte. Du brauchst nur drei Tatsachen: 0 + 0 = 0, 0 + 1 = 1 und 1 + 1 = 10, also 0 schreiben und 1 übertragen. Mit einem eingehenden Übertrag ist 1 + 1 + 1 = 11, du schreibst also 1 und überträgst 1. Die Rechnung steht im nächsten Absatz, deck ihn also zuerst ab.

Hier ist die Rechnung. Rechte Spalte: 1 + 1 = 10, 0 schreiben, 1 übertragen. Nächste: 0 + 1 plus Übertrag ist wieder 10, 0 schreiben, 1 übertragen. Nächste: 1 + 0 plus Übertrag, 10, 0 schreiben, 1 übertragen. Linke Spalte: 0 + 0 plus Übertrag ist 1. Das Ergebnis ist 1000, also 8, und 5 + 3 = 8. Drei der vier Spalten hatten einen Übertrag. Ein Taschenrechner, ein Spiel und eine Tabellenkalkulation machen am Ende genau das. In einem Prozessor erledigen ein paar Gatter jede Spalte, und die Szene beginnt mit derselben Summe. Probier dort dann 9 + 8. Dafür braucht man ein fünftes Bit.

Die rechte Spalte braucht nur zwei Gatter

Sieh dir die rechte Spalte für sich an. Das Ergebnisbit dort, die Summe, ist 1, wenn genau ein Eingang 1 ist. Das ist die XOR-Regel. Der Übertrag ist nur dann 1, wenn beide Eingänge 1 sind. Das ist die AND-Regel. Ein XOR-Gatter und ein AND-Gatter nebeneinander, die dieselben zwei Eingänge bekommen, addieren also zwei Bits. Diese kleine Schaltung ist ein Halbaddierer. „Halb“ ist er nur, weil er keinen Übertrag aus der Spalte rechts von ihm aufnehmen kann.

Die anderen Spalten haben drei Bits zu addieren

In jeder anderen Spalte treffen drei Bits zusammen: eins aus jeder Zahl und der Übertrag von rechts. Ein Volladdierer nimmt alle drei. Seine Summe ist A XOR B XOR Übertrag-ein, das ist 1, wenn eine ungerade Anzahl der drei 1 ist. Sein Übertrag-aus ist 1, wenn mindestens zwei davon 1 sind. Zwei Halbaddierer und ein OR-Gatter ergeben einen Volladdierer. Stell vier Volladdierer nebeneinander, verbinde jeden Übertrag-aus mit dem Übertrag-ein des Addierers links daneben, und du hast einen 4-Bit-Addierer. Jeder Übertrag muss von rechts nach links durchlaufen, bevor die letzte Spalte feststeht, deshalb heißt diese Bauart Ripple-Carry-Addierer. Echte Prozessoren addieren 64-Bit-Zahlen mit raffinierteren Schaltungen, die die Überträge vorausberechnen, aber die Regel in jeder Spalte ist dieselbe.

Was passiert, wenn das Ergebnis zu groß ist

Vier Bits fassen 0 bis 15. Addiere 9 und 8, dann ist das wahre Ergebnis 17 binär 10001, also fünf Bits. Ein Register, das nur vier Bits behält, speichert 0001, also 1, und der links übrig gebliebene Übertrag ist das Warnzeichen. Das ist ein Überlauf. 15 + 1 hinterlässt in vier Bits 0000. Prozessoren setzen dabei ein Flag, damit Programme es bemerken können. Die Subtraktion benutzt dasselbe Addierwerk. Um A − B zu berechnen, kehrt der Prozessor jedes Bit von B um und addiert 1, das ergibt das Zweierkomplement von B, addiert das dann zu A und verwirft den überzähligen Übertrag. Für 5 − 3 in vier Bits: 3 ist 0011, umgekehrt 1100, plus 1 ergibt 1101. Dann ist 0101 + 1101 = 10010, und mit vier Bits bleibt 0010, also 2.

Multiplizieren ist Verschieben und Addieren

Die Multiplikation entsteht aus denselben Teilen. Im Binärsystem schiebt eine Multiplikation mit 2 jedes Bit um eine Stelle nach links, so wie eine Multiplikation mit 10 im Dezimalsystem eine Null anhängt: Aus 0011 (3) wird 0110 (6). Bei 5 × 3 fällt auf, dass 3 = 2 + 1 ist. Also ist 5 × 3 = 5 × 2 + 5 × 1 = 1010 + 0101 = 1111, also 15. Eine Multiplizierschaltung verschiebt und addiert genau so und nimmt dabei die 1-Bits der zweiten Zahl eins nach dem anderen.