Decimal to Binary

Q: Kannst du mit Bitoperationen statt durch Division in Binärzahlen umwandeln?

Ja. n & 1 liefert das niedrigstwertige Bit und n >> 1 entfernt es. Das entspricht bei nicht negativen Zahlen n % 2 und n / 2 . Die Schleife und die Umkehrung bleiben gleich. Die Division ist leichter zu erklären, während die Shift-Variante in hardwarenaher Programmierung üblich ist.

EinsteigerMathe und Simulation Bitmanipulation

+10

Du erhältst eine nichtnegative ganze Zahl n. Gib ihre Binärdarstellung als Zeichenfolge aus 0en und 1en ohne führende Nullen zurück. Die einzige Zahl, deren Ergebnis mit 0 beginnt, ist null selbst, die als "0" geschrieben wird.

Funktion

toBinary(n: integer) → string

ninteger: die umzuwandelnde Zahl
Gibt zurückstring: die Binärziffern von n als Zeichenkette

Einschränkungen

0 ≤ n ≤ 2³¹-1
Erstelle die Zeichenkette selbst, anstatt eine integrierte Basisumwandlung aufzurufen.

Beispiele

Eingabe: n = 13
Ausgabe: "1101"
Erklärung: 13 = 8 + 4 + 1. An den Stellen für 8, 4, 2 und 1 stehen 1, 1, 0 und 1, was 1101 ergibt.

Eingabe: n = 0
Ausgabe: "0"
Erklärung: Null hat keine gesetzten Bits, aber die Antwort benötigt trotzdem eine Ziffer, also ist sie "0" und keine leere Zeichenfolge.

Eingabe: n = 64
Ausgabe: "1000000"
Erklärung: 64 ist 2^6, eine einzelne 1 an der 64er-Stelle, gefolgt von sechs 0en für die Stellen von 32 bis hinunter zu 1.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du n mit derselben Schleife in eine beliebige Basis von 2 bis 16 umwandeln und dabei die Buchstaben a bis f für die Ziffern über 9 verwenden?

Tipps

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

0 von 3 geöffnet

Lösung

Eine Binärzahl ist eine Summe von Zweierpotenzen, und jede Ziffer gibt an, ob eine Potenz in der Summe enthalten ist. Du kannst die Ziffern von oben bestimmen, indem du Zweierpotenzen subtrahierst, oder sie von unten ablesen, indem du die Reste wiederholter Division durch 2 verwendest. Die Divisionsschleife ist die Standardmethode: Sie muss nie zuerst die größte Potenz finden und funktioniert für jede Basis auf dieselbe Weise.

Zweierpotenzen von oben abziehen

Idee

So wandelst du von Hand um. Finde die größte Zweierpotenz, die in n passt; sie ist die erste Ziffer, eine 1. Gehe dann eine Zweierpotenz nach der anderen nach unten. Wenn die Zweierpotenz noch in den verbleibenden Wert passt, schreibe 1 und ziehe sie ab; andernfalls schreibe 0.

Für 13 ist die größte Zweierpotenz 8. Schreibe 1 und behalte 5. Dann passt 4 (1, behalte 1), 2 passt nicht (0), und 1 passt (1). Die Ziffern ergeben 1101. Die erste Ziffer ist immer eine 1, daher kann keine führende Null auftreten.

Beim Finden der größten Zweierpotenz ist Vorsicht geboten. Wenn du power verdoppelst, bis sie n überschreitet, kommt es zu einem Überlauf einer 32-Bit-Ganzzahl, sobald n ≥ 2^30, weil die nächste Zweierpotenz 2^31 ist. Wenn du nur verdoppelst, solange power ≤ n / 2, hältst du bei der richtigen Zweierpotenz an, ohne jemals n zu überschreiten. Eine 31-Bit-Zahl benötigt 31 Schritte, also O(log n).

Algorithmus

Wenn n 0 ist, gib "0" zurück.
Setze power auf 1 und verdopple es, solange power ≤ n / 2 gilt.
Solange power > 0 gilt: Wenn n ≥ power gilt, hänge 1 an und ziehe power von n ab; andernfalls hänge 0 an.
Halbiere power und wiederhole den Vorgang.
Gib die angehängten Ziffern zurück.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

Wiederholte Division durch 2

Idee

Die letzte Binärziffer von n gibt an, ob n ungerade ist; sie entspricht n % 2. Durch Division durch 2 und Weglassen des Rests wird jede Ziffer um eine Stelle nach rechts verschoben, sodass die nächste Ziffer zur letzten wird. Wiederhole dies, bis nichts mehr übrig ist, und sammle dabei jede Ziffer von der niedrigsten an.

Für 13: 13 ergibt den Rest 1, 6 den Rest 0, 3 den Rest 1 und 1 den Rest 1; danach ist die Zahl 0. Die Reste in dieser Reihenfolge sind 1, 0, 1, 1; umgekehrt gelesen ergeben sie 1101. Die Schleife endet, wenn die Zahl 0 erreicht, sodass die höchste ausgegebene Ziffer immer eine 1 ist und keine führende Null erscheint. Null selbst gelangt nie in die Schleife, weshalb sie eine eigene Prüfung benötigt.

Bei jedem Schritt wird die Zahl halbiert. Ein 31-Bit-Wert benötigt daher 31 Schritte; die Laufzeit beträgt O(log n), und die Ziffernfolge benötigt O(log n) Speicherplatz.

Algorithmus

Wenn n 0 ist, gib "0" zurück.
Solange n > 0 gilt, hänge n % 2 als Ziffer an und setze n auf n / 2, abgerundet.
Kehre die Ziffern um, da sie in umgekehrter Reihenfolge entstanden sind.
Gib sie als Zeichenkette zurück.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Stolperfallen und Grenzfälle

Die Schleife ist kurz, und die meisten falschen Antworten entstehen an ihren beiden Enden.

Für 0 eine leere Zeichenkette zurückgeben. Die Divisionsschleife wird für null nie ausgeführt, also prüfe den Wert zuerst.
Das Umkehren vergessen. Die Reste kommen beginnend mit der niedrigsten Ziffer an, daher ergibt 6 011 statt 110.
/ in einer Sprache verwenden, in der es einen Bruch zurückgibt, etwa JavaScript, Lua oder PHP. 13 / 2 muss zu 6 werden, also runde ab oder verwende Ganzzahldivision.
Die größte Potenz durch Verdoppeln ermitteln, bis sie größer als n ist. Für n = 2^31-1 passt die nächste Potenz, 2^31, nicht in eine 32-Bit-Ganzzahl.
In C zu wenig Speicher reservieren. Eine 31-Bit-Zahl benötigt 31 Zeichen plus das abschließende '\0'.

Häufige Fragen4

Wie wandelt man eine Dezimalzahl in eine Binärzahl um?

Teile die Zahl immer wieder durch 2 und notiere jeden Rest, bis die Zahl 0 erreicht. Lies die Reste vom letzten bis zum ersten. Für 13 lauten die Reste 1, 0, 1, 1, also ist 13 im Binärsystem 1101.

Warum werden die Reste in umgekehrter Reihenfolge gelesen?

Die erste Division durch 2 zeigt dir, ob die Zahl ungerade ist – das ist die letzte Binärziffer. Jede weitere Division enthüllt die nächste Ziffer links davon. Die Reste ergeben sich also mit der niedrigsten Ziffer zuerst, und du kehrst ihre Reihenfolge um, um die Zahl in der üblichen Schreibweise aufzuschreiben.

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

Bei jedem Schritt wird die Zahl halbiert, daher wird die Schleife einmal pro Binärziffer ausgeführt, also etwa log2(n)-mal. Das entspricht einer Laufzeit von O(log n), und der Antwortstring benötigt O(log n) Speicherplatz. Bei einer 32-Bit-Ganzzahl sind das höchstens 31 Schritte.

Kannst du mit Bitoperationen statt durch Division in Binärzahlen umwandeln?

Ja. n & 1 liefert das niedrigstwertige Bit und n >> 1 entfernt es. Das entspricht bei nicht negativen Zahlen n % 2 und n / 2. Die Schleife und die Umkehrung bleiben gleich. Die Division ist leichter zu erklären, während die Shift-Variante in hardwarenaher Programmierung üblich ist.

Python

def toBinary(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 13

Erwartet

"1101"