Ich versuche, die Formel zu finden, um die maximale Bitbreite zu berechnen, die erforderlich ist, um eine Summe von vorzeichenlosen Binärzahlen mit M n Bit zu enthalten. Vielen Dank!Maximale Bitbreite zum Speichern einer Summe von M n-Bit-Binärzahlen
Die maximal benötigte Bitbreite sollte
sein.ceil(log_2(M * (2^n - 1)))
Bearbeiten: Dank @MBurnham merke ich jetzt, dass es floor(log_2(M * (2^n - 1))) + 1 stattdessen sein sollte.
Hm ... Ich habe beide Formeln experimentell mit Wolfram Alpha getestet ... scheint, als wäre noch was los ... – bfung
@bfung Aus wie? – xunatai
zum Beispiel, für M = 9 und n = 3, Ihre vorgeschlagene Formel gibt 7. Wenn ich 0b111 für 9 mal in Wolfram Alpha hinzufügen, ist die Antwort = 6b111111. – bfung
Unter der Annahme positiver Ganzzahlen benötigen Sie floor (log2 (x)) + 1 Bits zum Speichern von x. und der größte Wert, den die Summe von m n-Bit-Zahlen erzeugen kann, wäre m * 2^n. Also ich glaube, die Formel
sein solltefloor(log2(m * 2^n)) + 1
Bits.
Die größte n-Bit-Nummer ist 2^n-1, nicht 2^n – mbschenkel
@mbschenkel für nur 1 Zahl, die Sie richtig haben, aber wenn Sie eine Summe aus zwei Zahlen haben, können Sie Werte zur nächsten Ziffer übertragen. Sie müssen also ein extra Bit für Übertragungen speichern – MBurnham
Sie kümmern sich schon darum mit dem Faktor 'm'. Wenn "B = 2^n-1" der größtmögliche Wert von Eins ist, dann ist "m * B" die größtmögliche Summe von "m" Summanden, nicht "m * (B + 1)". – mbschenkel
Wenn ich 2 Zahlen addiere, brauche ich 1 Bit mehr als die breitere der 2 Zahlen, um das Ergebnis zu speichern. Also, wenn ich 2 n-Bit-Zahlen addiere, brauche ich n + 1 Bits, um das Ergebnis zu speichern.
if I add another n-bit number, I need (n+1)+1 bits to store the result (that's 3 n-bit numbers added so far)
if I add another n-bit number, I need ((n+1)+1)+1 bits to store the result (that's 4 n-bit numbers added so far)
if I add another n-bit number, I need (((n+1)+1)+1)+1 bits to store the result (that's 5 n-bit numbers added so far)
Also, ich glaube, Ihre Formel ist
n + M - 1
Dies ist eine Obergrenze, aber nicht unbedingt das Minimum (trotz der Tatsache, dass OP nach Max fragt ...). Wenn Sie zwei Zahlen addieren, verwenden Sie nicht den vollen Bereich: z. B. 1 + 1 = 10, nicht 11, 1 + 1 + 1 = 11 und das dritte Bit überhaupt nicht. Dies ist jedoch für zweiwertige negative Zahlen unterschiedlich. – mbschenkel
gut, wenn ich zwei Ein-Bit-Zahlen addieren es bis zu zwei Bits nehmen. Wenn ich zwei zwei Bit-Zahlen addiere, kann es im schlimmsten Fall drei Bits für das Überrollen nehmen. Wenn ich zwei Drei-Bit-Zahlen addiere, benötigt der Worst-Case vier ... –
Wenn ich 1111 mit 1 ein Vier-Bit und ein 1-Bit addiere, benötigt es fünf als Ergebnis. Nicht anders als zwei einziffrige Dezimalzahlen können zweistellige Ergebnisse usw. benötigen. –