Binary to Decimal

Q: Wie hoch ist die Zeitkomplexität der Umwandlung von Binär- in Dezimalzahlen?

Beide Schleifen durchlaufen jedes der n Zeichen genau einmal und benötigen daher O(n) Zeit. Sie speichern nur eine oder zwei Zahlen, was O(1) zusätzlichem Speicherplatz entspricht. Bei einer Zeichenfolge mit 31 Zeichen sind das 31 Schritte.

EinsteigerMathe und Simulation Bitmanipulation

+10

Du erhältst eine Zeichenfolge s, die eine nichtnegative Zahl im Binärsystem darstellt und nur die Zeichen 0 und 1 verwendet. Gib den Wert dieser Zahl als gewöhnliche ganze Zahl zurück. Die Zeichenfolge enthält keine führenden Nullen, außer bei der Zahl null, die aus dem einzelnen Zeichen 0 besteht.

Funktion

toDecimal(s: string) → integer

sstring: die Binärziffern der Zahl
Gibt zurückinteger: der Wert von s als Ganzzahl

Einschränkungen

1 ≤ s.length ≤ 31
s enthält nur 0 und 1.
s beginnt mit 1, es sei denn, s ist "0".
Lies die Ziffern selbst aus, anstatt eine integrierte Basisumwandlung aufzurufen.

Beispiele

Eingabe: s = "1101"
Ausgabe: 13
Erklärung: Von rechts gelesen haben die Stellen die Werte 1, 2, 4 und 8. 1101 hat Einsen an den Stellen für 8, 4 und 1, und 8 + 4 + 1 = 13.

Eingabe: s = "0"
Ausgabe: 0
Erklärung: Eine einzelne 0 hat an keiner Stelle eine 1, daher ist ihr Wert 0.

Eingabe: s = "10000000"
Ausgabe: 128
Erklärung: Die einzige 1 hat rechts von sich sieben 0en, also steht sie an der Stelle mit dem Wert 2^7 = 128.

Weiterführende Frage

Kannst du mit derselben Schleife eine Zahl lesen, die in einer beliebigen Basis von 2 bis 16 geschrieben ist, wobei die Buchstaben a bis f für die Ziffern 10 bis 15 stehen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede Binärziffer steht für eine Zweierpotenz, die davon abhängt, wie weit sie vom rechten Ende entfernt ist. Du kannst diese Potenzen von rechts aus addieren oder die Zeichenfolge von links lesen und den Wert bei jedem Schritt verdoppeln. Die Verdopplungsschleife berechnet nie eine Potenz und ist dieselbe Schleife, die du zum Lesen von Dezimaltext verwendest, nur mit 2 statt 10.

Stellenwerte von rechts addieren

Idee

Die ganz rechte Ziffer ist 1 wert, die nächste 2, dann 4, 8 und so weiter, wobei sich der Wert mit jedem Schritt nach links verdoppelt. Die Zahl ist die Summe der Stellenwerte, an denen eine 1 steht. Gehe also vom letzten Zeichen zum ersten, behalte den aktuellen Stellenwert in power und addiere ihn, wenn die Ziffer 1 ist.

Bei 1101 triffst du auf 1 (addiere 1), 0 (überspringe 2), 1 (addiere 4) und 1 (addiere 8), was insgesamt 13 ergibt. Jede Ziffer wird genau einmal besucht, daher benötigt die Schleife O(n) Zeit und zwei Zahlen Speicher.

Achte auf die Größe von power. Bei einer Zeichenfolge mit 31 Ziffern erreicht der Wert bei der letzten Ziffer 2^30 und wird anschließend noch einmal auf 2^31 verdoppelt, was nicht in eine vorzeichenbehaftete 32-Bit-Ganzzahl passt. Speichere power in einer 64-Bit-Variablen oder verdopple den Wert nach der letzten Ziffer nicht mehr.

Algorithmus

Setze total = 0 und power = 1.
Gehe die Zeichenkette vom letzten Zeichen bis zum ersten durch.
Wenn das Zeichen 1 ist, addiere power zu total.
Verdopple power, bevor du eine Stelle nach links gehst.
Gib total zurück.

def toDecimal(s):
    total = 0
    power = 1  # the place value of the rightmost digit
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "1":
            total += power
        power *= 2
    return total

Verdoppeln und von links addieren

Idee

Lies die Zeichenkette von links und behalte value, die Zahl, die durch die bisher gelesenen Ziffern dargestellt wird. Wenn eine weitere Binärziffer angehängt wird, verschiebt sich jede vorherige Ziffer um eine Stelle nach links, wodurch sich ihr Wert verdoppelt; anschließend wird die neue Ziffer addiert. Jeder Schritt lautet also value = value * 2 + digit.

Bei 1101 nimmt value die Werte 1, dann 1 * 2 + 1 = 3, dann 3 * 2 + 0 = 6 und schließlich 6 * 2 + 1 = 13 an. Jedes Präfix der Zeichenkette ist eine kleinere Binärzahl, und die Schleife behält genau diese Zahl bei, sodass sie nach der letzten Ziffer den gesamten Wert enthält.

Der Wert wird nie größer als das Endergebnis. Bei einer 31-stelligen Zeichenkette bleibt er daher innerhalb von 2^31-1, und eine 32-Bit-Ganzzahl reicht aus. Die Ziffer erhält man, indem man vom Zeichencode den Code von '0' abzieht; dadurch wird '1' zu 1 und '0' zu 0. Das ist die übliche Methode, eine Zahl aus Text in einer beliebigen Basis einzulesen.

Algorithmus

Setze value = 0.
Wandle jedes Zeichen von links nach rechts in eine Ziffer um, indem du den Zeichencode von '0' subtrahierst.
Setze value = value * 2 + digit.
Gib value zurück.

def toDecimal(s):
    value = 0
    for ch in s:
        # Shift the digits read so far one place left, then add the new one.
        value = value * 2 + (ord(ch) - ord("0"))
    return value

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen durch die Laufrichtung oder den Typ der Ziffer.

Der Ziffer ganz links den Stellenwert 1 zuweisen. Die Stellenwerte beginnen am rechten Ende. Gehe also vom letzten Zeichen aus oder verwende die Verdopplungsschleife von links.
Das Zeichen statt der Ziffer addieren. In vielen Sprachen entspricht '1' der Zahl 49, daher ist value * 2 + '1' viel zu groß. Ziehe zuerst '0' ab.
Den Stellenwert überlaufen lassen. Wenn power nach der 31. Ziffer verdoppelt wird, ergibt sich 2^31, was bei einer 32-Bit-Ganzzahl zu einem Überlauf führt oder einen Absturz verursacht.
Jeden Stellenwert mit einer Fließkomma-Potenzfunktion berechnen. In C, C++ und Java gibt pow(2, k) einen double zurück, und das Ergebnis muss wieder in eine Ganzzahl umgewandelt werden.

Häufige Fragen3

Wie wandelt man Binärzahlen in Dezimalzahlen um?

Ordne jeder Ziffer einen Stellenwert zu: 1 für die ganz rechte, dann 2, 4, 8 und so weiter nach links. Addiere die Stellenwerte der Ziffern, die 1 sind. Für 1101 ergibt das 8 + 4 + 1 = 13.

Warum funktioniert das Verdoppeln des Werts?

Wenn man am Ende einer Binärzahl eine weitere Ziffer schreibt, rückt jede vorherige Ziffer um eine Stelle nach links, und jede Stelle ist doppelt so viel wert wie die rechts daneben. Der alte Wert verdoppelt sich also, und die neue Ziffer addiert 0 oder 1. Wenn man dies von der ersten bis zur letzten Ziffer wiederholt, erhält man die ganze Zahl.

Wie hoch ist die Zeitkomplexität der Umwandlung von Binär- in Dezimalzahlen?

Beide Schleifen durchlaufen jedes der n Zeichen genau einmal und benötigen daher O(n) Zeit. Sie speichern nur eine oder zwei Zahlen, was O(1) zusätzlichem Speicherplatz entspricht. Bei einer Zeichenfolge mit 31 Zeichen sind das 31 Schritte.

def toDecimal(s):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

s = "1101"

Erwartete Ausgabe