Während ich mich mehr und mehr mit der Theorie der Programmierung beschäftige, bin ich fasziniert und verblüfft von scheinbar einfachen Dingen. Mir ist klar, dass mein Verständnis der meisten grundlegenden Prozesse durch zirkuläre Logik gerechtfertigt ist

F : Wie funktioniert das?

A : Weil es so ist!

Ich hasse diese Erkenntnis! Ich liebe Wissen und darüber hinaus liebe ich das Lernen, was mich zu meiner Frage führt (auch wenn es eine breite Frage ist).

Frage:

Wie werden grundlegende mathematische Operatoren mit Programmiersprachen bewertet?

Wie wurden aktuelle Methoden verbessert?

Beispiel

var = 5 * 5; 

Meine Interpretation:

$num1 = 5; $num2 = 5; $num3 = 0;
while ($num2 > 0) {
    $num3 = $num3 + $num1;
    $num2 = $num2 - 1;
}
echo $num3;

Dies scheint sehr ineffizient zu sein. Mit höheren Faktoren ist diese Methode sehr langsam, während die standardmäßig eingebaute Methode augenblicklich ist. Wie würden Sie die Multiplikation ohne wiederholte Addition simulieren?

var = 5 / 5;

Wie geht das überhaupt? Ich kann mir keine Möglichkeit vorstellen, es buchstäblich 5 in 5 gleiche Teile aufzuteilen.

var = 5 ^ 5; 

Iterationen von Iterationen der Addition? Meine Interpretation:

$base = 5;
$mod = 5;
$num1 = $base;
while ($mod > 1) {

    $num2 = 5; $num3 = 0;
    while ($num2 > 0) {
        $num3 = $num3 + $num1;
        $num2 = $num2 - 1;
    }
    $num1 = $num3;
    $mod -=1;
}
echo $num3;

Auch dies ist EXTREM ineffizient, aber ich kann mir keinen anderen Weg vorstellen, dies zu tun. Dieselbe Frage erstreckt sich auf alle mathematisch relevanten Funktionen, die automatisch behandelt werden.

Um wirklich zu verstehen, wie Arithmetik in einem Computer funktioniert, müssen Sie in Assemblersprache programmiert haben. Vorzugsweise eines mit kleiner Wortgröße und ohne Multiplikations- und Divisionsanweisungen. So etwas wie der 6502.

Beim 6502 wird praktisch die gesamte Arithmetik in einem Register ausgeführt, das als Akkumulator bezeichnet wird. (Ein Register ist ein spezieller Speicherort im Prozessor, auf den schnell zugegriffen werden kann.) Wenn Sie also zwei Zahlen hinzufügen möchten, laden Sie die erste Zahl in den Akku und fügen dann die zweite Zahl hinzu.

Aber das ist zu einfach. Da der 6502 ein 8-Bit-Prozessor ist, kann er nur Zahlen von 0 bis 255 verarbeiten. Meistens möchten Sie mit größeren Zahlen arbeiten können. Sie müssen diese in Stücken, jeweils 8 Bits, hinzufügen. Der Prozessor verfügt über ein Carry-Flag, das gesetzt wird, wenn das Ergebnis des Hinzufügens von zwei Zahlen den Akku überläuft. Der Prozessor fügt dies hinzu, wenn er eine Addition vornimmt, sodass er verwendet werden kann, um "die 1 zu tragen", vorausgesetzt, Sie beginnen mit dem niederwertigsten Byte einer Zahl. Eine Multi-Byte-Erweiterung des 6502 sieht folgendermaßen aus:

1. CLC (Clear Carry Flag) löschen
2. Niedrigstwertiges Byte der ersten Zahl laden (LDA, Ladeakku)
3. Addiere das niederwertigste Byte der zweiten Zahl (ADC, addiere mit Übertrag)
4. Ergebnisbyte niedrigster Ordnung speichern (STA, Speicherakku)
5. Wiederholen Sie die Schritte 2 bis 4 mit Bytes höherer Ordnung
6. Wenn der Übertrag am Ende eingestellt ist, ist er übergelaufen. Ergreifen geeigneter Maßnahmen, z. B. Generieren einer Fehlermeldung (BCS / BCC, Verzweigen, wenn Übertrag gesetzt / gelöscht ist)

Die Subtraktion ist ähnlich, außer dass Sie zuerst den Übertrag einstellen, den SBC-Befehl anstelle des ADC verwenden und am Ende der Übertrag klar ist , wenn ein Unterlauf aufgetreten ist.

Aber warte! Was ist mit negativen Zahlen? Nun, mit dem 6502 werden diese in einem Format gespeichert, das als Zweierkomplement bezeichnet wird. Unter der Annahme einer 8-Bit-Zahl wird -1 als 255 gespeichert, denn wenn Sie 255 zu etwas hinzufügen, erhalten Sie im Akkumulator einen Wert weniger (zuzüglich eines Übertrags). -2 wird als 254 und so weiter gespeichert, bis -128, das als 128 gespeichert wird. Bei Ganzzahlen mit Vorzeichen wird also die Hälfte des Bereichs 0-255 eines Bytes für positive Zahlen und die Hälfte für negative Zahlen verwendet. (Mit dieser Konvention können Sie einfach das hohe Bit einer Zahl überprüfen, um festzustellen, ob es negativ ist.)

Stellen Sie sich das wie eine 24-Stunden-Uhr vor: Wenn Sie 23 zur Uhrzeit addieren, ist die Uhrzeit eine Stunde früher (am nächsten Tag). 23 ist also das modulare Äquivalent der Uhr zu -1.

Wenn Sie mehr als 1 Byte verwenden, müssen Sie größere Zahlen für Negative verwenden. 16-Bit-Ganzzahlen haben beispielsweise einen Bereich von 0 bis 65536. 65535 wird also verwendet, um -1 darzustellen, und so weiter, da das Hinzufügen von 65535 zu einer beliebigen Zahl zu einer Abnahme (plus einem Übertrag) führt.

Auf dem 6502 gibt es nur vier arithmetische Operationen: Addieren, Subtrahieren, Multiplizieren mit zwei (Verschiebung nach links) und Dividieren mit zwei (Verschiebung nach rechts). Multiplikation und Division können nur mit diesen Operationen ausgeführt werden, wenn es sich um Binärdateien handelt. Betrachten Sie zum Beispiel die Multiplikation von 5 (binär 101) und 3 (binär 11). Wie bei der dezimal langen Multiplikation beginnen wir mit der rechten Ziffer des Multiplikators und multiplizieren 101 mit 1, wobei wir 101 ergeben. Dann verschieben wir den Multiplikanden nach links und multiplizieren 1010 mit 1, wobei wir 1010 ergeben. Dann addieren wir diese Ergebnisse, wobei wir 1111 ergeben, oder 15. Da wir immer nur mit 1 oder 0 multiplizieren, multiplizieren wir nicht wirklich. Jedes Bit des Multiplikators dient lediglich als Flag, das angibt, ob der (verschobene) Multiplikand hinzugefügt werden soll oder nicht.

Die Division ist analog zur manuellen langen Division mit Trial-Divisoren, mit Ausnahme der Binärdivision. Wenn Sie durch eine Konstante dividieren, ist dies analog zur Subtraktion möglich: Anstatt durch X zu dividieren, multiplizieren Sie mit einer vorberechneten Wiedergabe von 1 / X, die das gewünschte Ergebnis plus einen Überlauf ergibt. Noch heute ist dies schneller als die Teilung.

Versuchen Sie nun, Gleitkomma-Berechnungen in Assembler durchzuführen oder Gleitkommazahlen in Assembler in schöne Ausgabeformate umzuwandeln. Und denken Sie daran, es ist 1979 und die Taktrate ist 1 MHz, also müssen Sie es so effizient wie möglich machen.

Die Dinge funktionieren auch heute noch so, außer bei größeren Wörtern und mehr Registern, und natürlich wird der Großteil der Mathematik jetzt von Hardware erledigt. Aber es geht immer noch genauso. Wenn Sie zum Beispiel die Anzahl der Verschiebungen und Additionen addieren, die für eine Multiplikation erforderlich sind, korreliert dies ziemlich gut mit der Anzahl der Zyklen, die für eine Hardware-Multiplikationsanweisung bei frühen Prozessoren erforderlich sind, die eine solche Anweisung wie die 6809 haben, bei der sie ausgeführt wurde im Mikrocode auf die gleiche Weise, wie Sie es manuell tun würden. (Wenn Sie ein größeres Transistorbudget haben, gibt es schnellere Möglichkeiten , die Verschiebungen und Additionen durchzuführen. Moderne Prozessoren führen diese Operationen also nicht sequentiell durch und können Multiplikationen in nur einem Zyklus ausführen.)

Am Ende werden grundlegende arithmetische Operationen in Hardware ausgeführt. Genauer gesagt, in der CPU (oder tatsächlich einem Teil davon)

Mit anderen Worten, es sind elektronische Schaltungen. Stellen Sie die entsprechenden Bits als Eingabe ein und Sie erhalten die entsprechenden Bits als Ausgabe. Es ist eine Kombination von grundlegenden Logikgattern.

http://en.wikipedia.org/wiki/Adder_%28electronics%29

http://en.wikipedia.org/wiki/Binary_multiplier

Dies alles wird in Don Knuths Die Kunst der Computerprogrammierung mit gründlicher Geduld behandelt.

Effiziente Algorithmen zum Addieren, Subtrahieren, Multiplizieren und Dividieren werden ausführlich beschrieben.

Sie können solche Dinge lesen, die die Unterteilung gut abdecken.

http://research.microsoft.com/pubs/151917/divmodnote.pdf

Es wird in Pikosekunden von elektronischen Schaltkreisen durchgeführt. Google 'Hardware-Multiplikator' usw. für Details. Moderne CPUs sind das äußerst komplexe Ergebnis jahrzehntelanger kontinuierlicher Verbesserungen.

BTW, da Sie nicht durch wiederholte Addition multiplizieren, warum würden Sie sich einen Computer vorstellen?

Dies ist keineswegs als gründliche Antwort gedacht, sondern soll Ihnen eine Vorstellung davon geben, wie die Dinge umgesetzt werden. Wie Sie wahrscheinlich wissen, werden Zahlen binär dargestellt. Zum Beispiel könnte ein Computer die Zahl 5 als 00000101 darstellen. Eine sehr grundlegende Operation, die ein Computer ausführen kann, ist das Verschieben nach links, was 00001010 als Dezimalzahl 10 ergibt. Wenn es zweimal nach rechts verschoben würde, wäre dies 00010100 (Dezimalzahl 20). Jedes Mal, wenn wir die Ziffern um eins nach links verschieben, verdoppeln wir die Zahl. Angenommen, ich hätte eine Zahl x und wollte sie mit 17 multiplizieren. Ich könnte x viermal nach links verschieben und dann x zum Ergebnis hinzufügen (16x + x = 17x). Dies wäre eine effiziente Methode, um eine Zahl mit 17 zu multiplizieren. Dies sollte Ihnen einen Einblick geben, wie ein Computer große Zahlen multiplizieren kann, ohne nur die wiederholte Addition zu verwenden.

Division kann Kombinationen von Addition, Subtraktion, Verschiebung nach rechts, Verschiebung nach links usw. verwenden. Es gibt auch zahlreiche Tricks, um Zahlen zu Exponenten zu erhöhen.

Als ich ein Kind war, lernte ich, wie man sich mit einem Stift und einem Papier vermehrt und teilt, ohne Zeit mit zu vielen Zusätzen zu verschwenden. Später erfuhr ich, dass Quadratwurzeln auch so berechenbar sind.

An der Universität habe ich gelernt, wie man trigonometrische und logarithmische Operationen mit einem Dutzend Multiplikationen, Divisionen und Additionen berechnet. Sie nannten es Taylor-Serie.

Davor gab mir mein Vater ein Buch, in dem diese komplexen Operationen bereits für Hunderte von Werten berechnet und in Tabellen dargestellt wurden. Es gab auch einige Erklärungen zum Schätzen des Fehlers, wenn Sie den Sinus eines Werts zwischen zwei berechneten Werten haben wollten.

Ganzzahlige Einheiten, Gleitkommaeinheiten, GPU und DSP implementieren nur all diese alten Techniken auf Silizium.

Ich werde versuchen, Ihnen eine Vorstellung davon zu geben, wie digitale Schaltungen zur Lösung von Problemen bei der digitalen Verarbeitung entwickelt wurden, indem Sie die von Ihnen gestellten Probleme verwenden: Wie implementieren CPUs Additionen und Multiplikationen.

Lassen Sie uns zunächst die direkte Frage aus dem Weg räumen: Wie bewertet eine Programmiersprache Multiplikationen und Additionen effizient? Die Antwort ist einfach, sie kompilieren sie in Multiplikation und fügen Anweisungen hinzu. Zum Beispiel der folgende Code:

a = 1 + 1;
b = a * 20;

wird einfach so kompiliert:

ADD 1 1  a
MUL a 20 b

(Beachten Sie, dass die obige Baugruppe der Einfachheit halber für eine imaginäre CPU gedacht ist, die nicht existiert).

An diesem Punkt stellen Sie fest, dass die obige Antwort das Problem einfach verschiebt und es durch Hardware-Magie löst. Die Folgefrage ist natürlich, wie diese Hardware-Magie funktioniert.

Schauen wir uns zuerst das einfachere Problem an: Addition.

Zuerst machen wir ein bekanntes Problem, indem wir 10 Zahlen zur regulären Basis hinzufügen:

 17
+28

Der erste Schritt wäre, 7 und 8 zu addieren. Dies ergibt jedoch 15, was mehr als eine einzelne Ziffer ist. Also tragen wir die 1:

(1)
 17
+28
= 5

Nun addieren wir 1, 1 und 2:

 17
+28
=45

Daraus ergeben sich folgende Regeln:

1. Wenn das Ergebnis der Addition mehr als eine Ziffer ist, behalten wir die niedrigstwertige Ziffer bei und übertragen die höchstwertige Ziffer nach vorne

2. Wenn wir eine Ziffer in unsere Spalte übertragen haben, fügen wir sie zusammen mit den Zahlen hinzu, die wir hinzufügen

Nun ist es an der Zeit, die obigen Regeln in der Basis 2 - Boolesche Algebra - zu interpretieren.

Also addieren wir in der Booleschen Algebra 0 und 1 = 1. Addieren von 0 und 0 = 0. Addieren von 1 und 1 = 10, was mehr als eine Ziffer ist, also tragen wir die 1 vor.

Daraus können wir eine Wahrheitstabelle erstellen:

a b  |  sum  carry
-------------------
0 0  |   0     0
0 1  |   1     0
1 0  |   1     0
1 1  |   0     1

Daraus können wir zwei Schaltungen / Boolesche Gleichungen konstruieren - eine für die Ausgabe der Summe und eine für die Ausgabe des Übertrags. Am einfachsten ist es, alle Eingaben aufzulisten. Jede Wahrheitstabelle, egal wie groß und komplex, kann in dieser Form ausgedrückt werden:

(AND inputs in first row) OR (AND of inputs in second row) OR ...

Dies ist im Grunde die Summe der Produktformen. Wir betrachten nur Ausgaben, die zu einer 1 führen, und ignorieren die Nullen:

sum = (NOT a AND b) OR (a AND NOT b)

Ersetzen wir das UND ODER und NICHT durch die Symbole der Programmiersprache, um die Lesbarkeit zu verbessern:

sum = (!a & b) | (a & !b)

Grundsätzlich haben wir die Tabelle folgendermaßen konvertiert:

a b  |  sum  equation
-------------------
0 0  |   0   
0 1  |   1   (!a & b)
1 0  |   1   (a & !b)
1 1  |   0   

Dies kann direkt als Schaltung implementiert werden:

                _____
 a ------------|     |
    \          | AND |-.     ____
     \  ,-NOT--|_____|  \   |    |
      \/                 `--| OR |----- sum
      /\        _____    ,--|____|
     /  `-NOT--|     |  /
    /          | AND |-`
 b ------------|_____|

Beobachter würden an dieser Stelle bemerken, dass die obige Logik tatsächlich als einzelnes Gatter implementiert werden kann - ein XOR-Gatter, das in geeigneter Weise das von unserer Wahrheitstabelle geforderte Verhalten aufweist:

                _____
 a ------------|     |
               | XOR |---- sum
 b ------------|_____|

Wenn Ihre Hardware Ihnen jedoch kein XOR-Gatter bietet, definieren und implementieren Sie es in den obigen Schritten in Bezug auf AND-, OR- und NOT-Gatter.

Wie Sie Logikgatter in tatsächliche Hardware umwandeln, hängt von der Hardware ab, über die Sie verfügen. Sie können unter Verwendung verschiedener physikalischer Mechanismen implementiert werden, solange der Mechanismus eine Art Schaltverhalten bereitstellt. Logikgatter wurden mit allem implementiert, von Wasserstrahlen oder Luftstößen (Fluidik) über Transisitoren (Elektronik) bis hin zu fallenden Murmeln. Es ist ein großes Thema für sich, also beschönige ich es einfach und sage, dass es möglich ist, logische Gatter als physische Geräte zu implementieren.

Jetzt machen wir dasselbe für das Übertragsignal. Da es nur eine Bedingung gibt, in der das Übertragsignal wahr ist, lautet die Gleichung einfach:

carry = a & b

So tragen ist einfach:

                _____
 a ------------|     |
               | AND |---- carry
 b ------------|_____|

Wenn wir sie miteinander kombinieren, erhalten wir das, was als Halbaddierer bekannt ist:

                _____
 a ------;-----|     |
         |     | XOR |---- sum
 b --;---|-----|_____|
     |   |      _____
     |   '-----|     |
     |         | AND |---- carry
     '---------|_____|

Die Gleichungen für die obige Schaltung sehen übrigens so aus:

sum = a ^ b
carry = a & b

Dem Halbaddierer fehlt etwas. Wir haben die erste Regel implementiert - wenn das Ergebnis mehr als eine Ziffer als Übertrag ist, aber wir haben die zweite Regel nicht implementiert - wenn es einen Übertrag gibt, addieren Sie sie zusammen mit den Zahlen.

Um einen Volladdierer zu implementieren, eine Addierschaltung, die Zahlen mit mehr als einer Ziffer addieren kann, müssen wir eine Wahrheitstabelle definieren:

a b c  |  sum  carry
---------------------
0 0 0  |   0     0
0 0 1  |   1     0
0 1 0  |   1     0
0 1 1  |   0     1
1 0 0  |   1     0
1 0 1  |   0     1
1 1 0  |   0     1
1 1 1  |   1     1

Die Gleichung für die Summe lautet nun:

sum = (!a & !b & c) | (!a & b & !c) | (a & !b & !c) | (a & b & c)

Wir können den gleichen Prozess durchlaufen, um die Gleichung herauszuformulieren und zu vereinfachen und sie als Schaltung usw. zu interpretieren, wie wir es oben getan haben, aber ich denke, diese Antwort wird zu lang.

Inzwischen sollten Sie eine Vorstellung davon bekommen, wie digitale Logik aufgebaut ist. Es gibt andere Tricks, die ich nicht erwähnt habe, wie Karnaugh-Maps (zur Vereinfachung von Wahrheitstabellen) und Logik-Compiler wie Espresso (damit Sie Boolesche Gleichungen nicht von Hand ausrechnen müssen), aber die Grundlegenden sind im Grunde die, die ich habe oben umrissen:

1. Zerlegen Sie das Problem, bis Sie auf Einzelbitebene (Ziffernebene) arbeiten können.

2. Definieren Sie die gewünschten Ausgaben mithilfe einer Wahrheitstabelle.

3. Konvertieren Sie die Tabelle in eine Boolesche Gleichung und vereinfachen Sie die Gleichung.

4. Interpretieren Sie die Gleichung als logisches Gatter.

5. Wandeln Sie Ihre Logikschaltung in echte Hardwareschaltungen um, indem Sie Logikgatter implementieren.

Auf diese Weise werden grundlegende (oder eher einfache) Probleme wirklich gelöst - viele, viele Wahrheitstabellen. Die eigentliche kreative Arbeit besteht darin, eine komplexe Aufgabe wie die MP3-Dekodierung auf Bit-Ebene aufzubrechen, damit Sie mit Wahrheitstabellen daran arbeiten können.

Entschuldigung, ich habe keine Zeit zu erklären, wie die Multiplikation implementiert wird. Sie können versuchen, einen Riss zu machen, indem Sie herausfinden, wie lange die Multiplikation funktioniert, und sie dann als Binärdatei interpretieren und dann versuchen, sie in Wahrheitstabellen zu zerlegen. Oder Sie können Wikipedia lesen: http://en.wikipedia.org/wiki/Binary_multiplier

Grundrechenarten werden mit hocheffizienten Montageanweisungen ausgeführt.

Komplexere (oder abstraktere) Anweisungen werden entweder in Assemblern mit Schleifenmechanismen ausgeführt oder in Standardbibliotheken behandelt.

Während Sie am College Mathematik studieren, lernen Sie Dinge wie Lambda-Kalkül und Big-O-Notation. All diese und viele weitere werden von Programmierern verwendet, um effiziente Algorithmen zu evaluieren und zu erstellen. Wie auch immer, die grundlegenden Aufgaben werden normalerweise auf niedriger Ebene ausgeführt, z. B. in der Montage oder in c mit Zeigern.

Eine gute Einführung in dieses Thema ist "Code" von Charles Petzold.

Holen Sie sich ein Buch wie Fundamentals of Digital Logic ... , das meiner Meinung nach für Freshman / Sophomore EE-Studenten immer noch Standard ist es). Das wird Sie durch die Addierer und Multiplikatoren führen und Ihnen genug Hintergrundwissen geben, um einige der Prinzipien zu verstehen, die hinter der Arbeit der Hardware stehen.

Ihre Antwort wird kurzfristig lauten: "Weil es unzählige Teile einer einfacheren Logik zusammenfügt, um dieses komplexe Verhalten hervorzurufen", anstatt "weil es das tut".

Wenn Sie versuchen möchten, alle Prinzipien zu verstehen, wie Programme kompiliert und ausgeführt werden, gehen Sie dazu in Verbindung, damit Sie letztendlich sehen können, wie sich alles in der Mitte trifft.

Hier gibt es viele gute Antworten. Sie haben auch mit der richtigen Idee begonnen: Komplexe Operationen wie die Multiplikation bauen auf einfacheren Operationen auf. Wie Sie vermutet haben, gibt es schnellere Möglichkeiten, ohne Multiplikationsanweisung zu multiplizieren, als mit einer Reihe von Additionen. Jede Multiplikation kann als Summe kleinerer Multiplikationen oder als Kombination von Verschiebungen und Additionen implementiert werden. Beispiele:

a = 5 + 5 + 5 + 5 + 5;           // 5*5, but takes 5 operations
b = (5 << 2) + 5;                // 5*5 in only 2 operations
c = (41 << 4) + (41 << 2) + 41   // 41*21 in 4 operations

Die Division kann ebenfalls in kleinere Geschäftsbereiche unterteilt werden. XOR (^) ist eine integrierte Anweisung für jeden Prozessor, den ich mir jemals angesehen habe. Sie kann jedoch auch als Kombination aus AND, OR und NOT implementiert werden.

Ich habe jedoch das Gefühl, dass bestimmte Antworten für Sie weniger befriedigend sind als eine allgemeine Vorstellung davon, welche Arten von Anweisungen ein Prozessor bereitstellt und wie diese Anweisungen zu komplexeren Operationen kombiniert werden können. Es gibt nichts Besseres für diese Art von Neugier als eine gesunde Portion Assemblersprache. Hier ist eine sehr verständliche Einführung in die MIPS-Assemblersprache.

So könnte ein moderner Prozessor die Multiplikation zweier 64-Bit-Ganzzahlen implementieren:

Sie wissen, wie man eine Long-Hand-Multiplikation durchführt. Um zwei 10-stellige Zahlen zu multiplizieren, multiplizieren Sie jeweils eine 10-stellige Zahl mit den 10 Stellen der anderen Zahl, schreiben das 11-stellige Ergebnis untereinander und verschieben es und addieren dann die gesamte Zahl.

Ein moderner Prozessor erledigt dies mit allen 64 mal 64 Bits. Eine Multiplikation von zwei Einzelbitzahlen ist jedoch sehr einfach: 1 x 1 = 1, alle anderen Produkte sind Null. Dies wird mit einem logischen und implementiert. Und im Gegensatz zum Dezimalprodukt, bei dem das Ergebnis zweistellig sein kann, ist ein Binärprodukt aus einzelnen Bitnummern immer ein Bit.

Jetzt haben Sie 64 Zeilen mit 64 Bits, die hinzugefügt werden müssen. Aber 64 Additionen von 64-Bit-Zahlen sind langweilig. Der Prozessor verwendet also entweder einen 3/2-Addierer oder einen 7/3-Addierer: Wenn Sie 3 einzelne Bitnummern hinzufügen, kann das Ergebnis 0, 1, 2 oder 3 sein, was in zwei Bits passt. Wenn Sie 7 einzelne Bitnummern hinzufügen, ist das Ergebnis eine Zahl von 0 bis 7, die durch 3 Bits dargestellt werden kann. IBM behauptet, dass sie einen 7/3-Addierer mit nur 18 primitiven Schaltkreisen erstellen können (PowerPC-Dokumentation). Ich wette, Intel und ARM können dies ebenfalls.

Sie haben 4096 Bits, gruppieren sie in ungefähr 600 Gruppen von 7 Bits an den gleichen Bitpositionen und verwenden ungefähr 600 7/3-Addierer, um das Ergebnis von 4096 Bits auf weniger als 2.000 zu reduzieren. Dann machst du dasselbe immer wieder, bis du Paare von Bits hast, die in einen normalen Volladdierer eingespeist werden können.