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 jeder zweite Schritt die Anzahl halbiert: 61 Schritte für n = 2^31 - 1 . Das Zählen der Binärziffern mit integrierten Bitbefehlen ist O(1) .

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

2^31 - 1 , das sind einunddreißig Einsen im Binärsystem. Dafür sind 31 Subtraktionen und 30 Halbierungen nötig, insgesamt also 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 Ausgangszahl
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 geht 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, 4 Schritte.

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

Weiterführende Frage

Angenommen, eine ungerade Zahl kann ebenfalls um 1 erhöht 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

Im Binärsystem wird beim Halbieren die letzte Ziffer entfernt, und wenn man von einer ungeraden Zahl 1 subtrahiert, wird ihre letzte 1 zu einer 0. Für n > 0 ist die Antwort also die Anzahl der Binärziffern plus die Anzahl der Einsen minus eins. Die Regel direkt anzuwenden ist ebenfalls schnell: höchstens 61 Schritte.

Führe den Prozess aus

Idee

Führe die Regel aus und zähle die Schritte. Für 14 durchläuft die Schleife 7, 6, 3, 2, 1 und 0: sechs Schritte.

Eine Subtraktion macht eine ungerade Zahl immer gerade, daher erfolgt mindestens jeder zweite Schritt eine Halbierung. Eine Zahl unter 2^31 wird höchstens 30-mal halbiert, bevor sie 1 erreicht. Mit einer Subtraktion vor jeder Halbierung und einer am Ende läuft die Schleife höchstens 61-mal. Für n = 0 wird die Schleife nie ausgeführt und die Antwort ist 0.

Algorithmus

Setze steps auf 0.
Solange n > 0: 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

Bei jedem Schritt wird entweder die letzte Binärziffer entfernt oder eine abschließende 1 in 0 umgewandelt. 14 ist 1110: Halbieren ergibt 111, und davon abziehen ergibt 110. Jede 1 muss einmal gelöscht werden, was eine Subtraktion pro 1 kostet. Jede Ziffer muss entfernt werden, jeweils durch einmaliges Halbieren, außer der führenden Eins: Wenn nur noch 1 übrig ist, ergibt ihre Subtraktion bereits 0. Die Antwort lautet also length - 1 + ones, und für 14 ergibt das 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust und Swift verfügen über integrierte Funktionen für beide Zählungen (führende Nullen und gesetzte Bits), die auf den meisten Prozessoren zu einzelnen Befehlen kompiliert werden. Andere Sprachen lesen die Ziffern in einer Schleife mit höchstens 31 Durchläufen mithilfe von % 2 aus. Behandle zuerst n = 0: Es hat kein gesetztes Bit, an dem die Formel ansetzen 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

n = 0 in der Bitformel vergessen. length - 1 + ones ergibt -1, und die Anzahl führender Nullen bei 0 kann undefiniert sein (__builtin_clz(0) in C).
Eine Halbierung für die führende Ziffer mitzählen. Durch eine Subtraktion wird 1 zu 0, also benötigt 8 = 1000 4 - 1 + 1 = 4 Schritte, nicht 5.
Für eine ungerade Zahl n = (n-1) / 2 schreiben und einen Schritt zählen. Diese Zeile führt zwei Schritte aus, daher ergibt sich für 14 4 statt 6.
Solange n > 1 in einer Schleife laufen. Dadurch wird vor dem letzten Schritt abgebrochen, der 1 in 0 umwandelt.

Häufige Fragen3

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

Die Ausführung des Prozesses dauert O(log n), da mindestens jeder zweite Schritt die Anzahl halbiert: 61 Schritte für n = 2^31 - 1. Das Zählen der Binärziffern mit integrierten Bitbefehlen ist O(1).

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

2^31 - 1, das sind einunddreißig Einsen im Binärsystem. Dafür sind 31 Subtraktionen und 30 Halbierungen nötig, insgesamt also 61 Schritte. Keine kleinere Zahl hat gleichzeitig so viele Stellen und so viele Einsen.

Warum ist Halbieren dasselbe wie eine Rechtsverschiebung?

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

def numberOfSteps(n):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

n = 14

Erwartete Ausgabe