Steps to Reduce a Number to Zero

Q: Wie hoch ist die Zeitkomplexität beim Reduzieren einer Zahl auf null?

Die Ausführung des Prozesses dauert O(log n) , da mindestens bei jedem zweiten Schritt die Anzahl halbiert wird. Für n = 2^31 - 1 sind das 61 Schritte. Das Zählen der Binärziffern mit integrierten Bitbefehlen dauert O(1) .

Q: Wie lautet die Formel für die Anzahl der Schritte?

Für n > 0 ist die Antwort die Länge der Binärdarstellung von n , minus eins, plus die Anzahl der 1-Bits. Jedes 1-Bit kostet eine Subtraktion und jede Ziffer unterhalb der führenden Eins kostet eine Halbierung. Für n = 0 lautet die Antwort 0 .

Q: Welche Zahl unter 2^31 benötigt die meisten Schritte?

2^31 - 1 , also dreißig-eins Einsen im Binärsystem. Es benötigt 31 Subtraktionen und 30 Halbierungen, insgesamt 61 Schritte. Keine kleinere Zahl hat gleichzeitig so viele Stellen und so viele Einsen.

EinsteigerBitmanipulation Mathe und Simulation

+10

Beginne mit einer nichtnegativen ganzen Zahl n und wende wiederholt eine Regel an, bis sie 0 erreicht: Ist die Zahl gerade, teile sie durch 2; ist sie ungerade, ziehe 1 ab. Jede Anwendung der Regel ist ein Schritt. Gib die Anzahl der benötigten Schritte zurück.

Funktion

numberOfSteps(n: integer) → integer

ninteger: die Startzahl
Gibt zurückinteger: die Anzahl der Schritte, bis die Zahl 0 erreicht

Einschränkungen

0 ≤ n ≤ 2³¹ - 1

Beispiele

Eingabe: n = 14
Ausgabe: 6
Erklärung: Die Zahl durchläuft 14 → 7 → 6 → 3 → 2 → 1 → 0: drei Halbierungen und drei Subtraktionen, 6 Schritte.

Eingabe: n = 8
Ausgabe: 4
Erklärung: 8 → 4 → 2 → 1 → 0. Eine Zweierpotenz wird dreimal halbiert und benötigt am Ende eine Subtraktion, also 4 Schritte.

Eingabe: n = 123
Ausgabe: 12
Erklärung: 123 ist im Binärsystem 1111011: sieben Ziffern und sechs Einsen. Die sechs Einsen erfordern sechs Subtraktionen und die sechs Ziffern unter der führenden Eins sechs Halbierungen, also 12 Schritte.

+12 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, eine ungerade Zahl kann auch um 1 erhöht statt verringert werden. Wie viele Schritte sind mindestens nötig, um 0 zu erreichen, und welche Wahl ist für 15 richtig?

Tipps

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

0 von 3 geöffnet

Lösung

Die Regel auszuführen ist bereits schnell: Bei jeder Halbierung wird die Zahl halbiert, sodass selbst 2^31 - 1 nur 61 Schritte benötigt. Interessant ist, was die Regel mit den Binärziffern macht. Beim Halbieren fällt die letzte Ziffer weg, und wenn man von einer ungeraden Zahl 1 subtrahiert, wird ihre letzte 1 zu einer 0. Die Antwort ist also die Anzahl der Ziffern plus die Anzahl der Einsen minus eins.

Führe den Prozess aus

Idee

Führe aus, was die Anweisung besagt. Solange n größer als 0 ist, halbiere es, wenn es gerade ist, ziehe 1 ab, wenn es ungerade ist, und zähle den Schritt. Für 14 durchläuft die Schleife 7, 6, 3, 2, 1 und 0 — sechs Schritte.

Die Schleife ist kurz, weil eine Subtraktion eine ungerade Zahl immer gerade macht, sodass mindestens jeder zweite Schritt eine Halbierung ist. Eine Zahl kleiner als 2^31 wird höchstens 30-mal halbiert, bevor sie 1 erreicht. Mit einer Subtraktion vor jeder Halbierung und einer am Ende wird die Schleife höchstens 61-mal ausgeführt.

Für die Eingabe 0 ist kein Sonderfall nötig: Die Schleifenbedingung ist sofort nicht erfüllt und die Antwort lautet 0.

Algorithmus

Setze steps auf 0.
Solange n > 0 gilt: Wenn n gerade ist, setze n auf n / 2, andernfalls auf n-1.
Addiere jedes Mal 1 zu steps.
Gib steps zurück.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

Anzahl der Binärziffern

Idee

Verfolge den Ablauf im Binärsystem. 14 ist 1110. Halbieren entfernt die letzte Ziffer: 111. Subtrahiert man 1 von einer ungeraden Zahl, wird ihre letzte Ziffer, eine 1, gelöscht: 110. Jeder Schritt entfernt also entweder die letzte Ziffer oder wandelt eine abschließende 1 in eine 0 um.

Zähle nun. Jede 1 in der Zahl muss einmal gelöscht werden, was eine Subtraktion pro 1 kostet. Jede Ziffer muss entfernt werden, was eine Halbierung pro Ziffer kostet, außer der führenden Eins: Wenn nur noch 1 übrig ist, ergibt die Subtraktion, die sie löscht, bereits 0. Die Antwort lautet also length - 1 + ones. Für 14 = 1110 ergibt das 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust und Swift verfügen über eingebaute Funktionen für beide Zählungen (eine Zählung der führenden Nullen und eine Popcount-Funktion), die auf den meisten Prozessoren zu einzelnen Instruktionen kompiliert werden. In den anderen Sprachen wird n binär dargestellt und die Anzahl der Zeichen gezählt oder die Ziffern mit % 2 ausgelesen; das ist eine Schleife mit höchstens 31 Durchläufen. Gib zuerst 0 für n = 0 zurück: Es gibt kein gesetztes Bit, auf das sich die Formel stützen könnte.

Algorithmus

Wenn n == 0, gib 0 zurück.
Bestimme length, die Anzahl der Binärziffern von n.
Bestimme ones, die Anzahl der 1-Bits.
Gib length - 1 + ones zurück.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Stolperfallen und Grenzfälle

Die Regel besteht aus zwei Zeilen. Die Fehler liegen bei den Grenzfällen und beim Off-by-one-Fehler in der Formel.

n = 0 in der Bitformel vergessen. Ohne Ziffern und ohne Einsen ergibt length - 1 + ones den Wert -1, und die Anzahl führender Nullen bei 0 ist möglicherweise undefiniert (__builtin_clz(0) in C).
Eine Halbierung für die führende Ziffer zählen. 1 wird durch eine Subtraktion zu 0, also benötigt 8 = 1000 4 - 1 + 1 = 4 Schritte, nicht 5.
Zwei Schritte zu einem zusammenfassen. Wenn man für eine ungerade Zahl n = (n-1) / 2 schreibt, werden gleichzeitig eine Subtraktion und eine Halbierung ausgeführt. Daher müssen zum Zähler 2 statt 1 addiert werden. Andernfalls ergibt sich für 14 4 statt 6.
Die Schleife mit n > 1 ausführen. Dadurch wird sie einen Schritt zu früh beendet, denn der letzte Schritt wandelt 1 in 0 um. Die Schleife muss laufen, bis n gleich 0 ist.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Reduzieren einer Zahl auf null?

Die Ausführung des Prozesses dauert O(log n), da mindestens bei jedem zweiten Schritt die Anzahl halbiert wird. Für n = 2^31 - 1 sind das 61 Schritte. Das Zählen der Binärziffern mit integrierten Bitbefehlen dauert O(1).

Wie lautet die Formel für die Anzahl der Schritte?

Für n > 0 ist die Antwort die Länge der Binärdarstellung von n, minus eins, plus die Anzahl der 1-Bits. Jedes 1-Bit kostet eine Subtraktion und jede Ziffer unterhalb der führenden Eins kostet eine Halbierung. Für n = 0 lautet die Antwort 0.

Welche Zahl unter 2^31 benötigt die meisten Schritte?

2^31 - 1, also dreißig-eins Einsen im Binärsystem. Es benötigt 31 Subtraktionen und 30 Halbierungen, insgesamt 61 Schritte. Keine kleinere Zahl hat gleichzeitig so viele Stellen und so viele Einsen.

Warum entspricht Halbieren einer Rechtsverschiebung?

Eine Binärzahl ist eine Summe von Zweierpotenzen. Wenn du eine gerade Zahl durch 2 teilst, verringert sich jede Potenz um eins. Dadurch verschiebt sich jede Ziffer um eine Stelle nach rechts und die letzte 0 fällt weg. Genau das bewirkt n >> 1, daher kannst du die Halbierung auf beide Arten schreiben.

Python

def numberOfSteps(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 14

Erwartet