Mindestanzahl an Bitwechseln zur Konvertierung einer Zahl

2220. Mindestanzahl an Bitwechseln zur Konvertierung einer Zahl

Schwierigkeit:Einfach

Themen:Bit-Manipulation

Ein Bit-Flip einer Zahl x besteht darin, ein Bit in der binären Darstellung von x auszuwählen und es entweder von 0 auf 1 oder von 1 auf 0 umzudrehen.

• Zum Beispiel ist forx = 7, die binäre Darstellung ist 111 und wir können ein beliebiges Bit (einschließlich aller nicht gezeigten führenden Nullen) auswählen und es umdrehen. Wir können das erste Bit von rechts umdrehen, um 110 zu erhalten, das zweite Bit von rechts umdrehen, um 101 zu erhalten, das fünfte Bit von rechts (eine führende Null) umdrehen, um 10111 zu erhalten usw.

Angenommen zwei ganze Zahlen Start und Ziel, geben Sie die Mindestanzahl von Bit-Flips zurück, um Start in Ziel umzuwandeln.

Beispiel 1:

• Eingabe:Start = 10, Ziel = 7
• Ausgabe: 3
• Erklärung: Die binäre Darstellung von 10 und 7 ist 1010 bzw. 0111. Wir können 10 in 3 Schritten in 7 umwandeln:
  • Das erste Bit von rechts umdrehen: 1010 -> 1011.
  • Das dritte Bit von rechts umdrehen: 1011 -> 1111.
  • Das vierte Bit von rechts umdrehen: 1111 -> 0111.
  • Es kann gezeigt werden, dass wir 10 nicht in weniger als 3 Schritten in 7 umwandeln können. Daher geben wir 3 zurück.

Beispiel 2:

• Eingabe:Start = 3, Ziel = 4
• Ausgabe: 3
• Erklärung: Die binäre Darstellung von 3 und 4 ist 011 bzw. 100. Wir können 3 in 4 in 3 Schritten umwandeln:
  • Das erste Bit von rechts umdrehen: 011 -> 010.
  • Das zweite Bit von rechts umdrehen: 010 -> 000.
  • Drittes Bit von rechts umdrehen: 000 -> 100.
  • Es zeigt sich, dass wir 3 nicht in weniger als 3 Schritten in 4 umwandeln können. Daher geben wir 3 zurück.

Einschränkungen:

• 0 <= Start, Ziel <= 10⁹

Hinweis:

1. Wenn der Wert eines Bits in Start und Ziel unterschiedlich ist, müssen wir dieses Bit umdrehen.
2. Erwägen Sie die Verwendung der XOR-Operation, um zu bestimmen, welche Bits einen Bit-Flip benötigen.

Lösung:

Wir müssen bestimmen, um wie viele Bitpositionen sich zwischen Start und Ziel unterscheiden. Dies lässt sich leicht mit der XOR-Operation (^) erreichen, die für jede Bitposition, an der sich die beiden Zahlen unterscheiden, eine 1 zurückgibt.

Schritte:

1. Führen Sie die XOR-Operation zwischen Start und Ziel durch. Das Ergebnis wird eine Zahl sein, die an allen Positionen, an denen Start und Ziel unterschiedlich sind, Einsen hat.
2. Zählen Sie, wie viele Einsen in der binären Darstellung des Ergebnisses (d. h. der Hamming-Distanz) vorhanden sind.
3. Die Anzahl der Einsen gibt uns die Mindestanzahl der benötigten Bit-Flips an.

Lassen Sie uns diese Lösung in PHP implementieren: 2220. Mindestanzahl an Bitwechseln zum Konvertieren einer Zahl

  
  
  Erläuterung:



Die ^ (XOR)-Operation vergleicht jedes Bit von Start und Ziel. Wenn die Bits unterschiedlich sind, ist das entsprechende Bit im Ergebnis 1.
Wir zählen dann die Anzahl der Einsen im Ergebnis, was die Anzahl der unterschiedlichen Bits ergibt, d. h. die Anzahl der erforderlichen Bitwechsel.
Die & 1-Operation prüft, ob das letzte Bit 1 ist, und >>= 1 verschiebt die Zahl nach rechts, um das nächste Bit zu verarbeiten.



  
  
  Zeitkomplexität:



Die Zeitkomplexität beträgt (O(log N)), wobei (N) der größere Wert von Start oder Ziel ist, da wir jedes Bit der Zahl überprüfen. Im schlimmsten Fall durchlaufen wir alle Bits einer 32-Bit-Ganzzahl (da PHP 5.6 je nach System mit 32-Bit- oder 64-Bit-Ganzzahlen arbeitet).



  
  
  Ausgabe:



Für Start = 10 und Ziel = 7 ist die Ausgabe 3.
Für Start = 3 und Ziel = 4 ist die Ausgabe 3.


Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
        
Das obige ist der detaillierte Inhalt vonMindestanzahl an Bitwechseln zur Konvertierung einer Zahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!