Retournements de bits minimum pour convertir le nombre

2220. Retournements de bits minimum pour convertir le nombre

Difficulté :Facile

Sujets : Manipulation des bits

Un retournement de bits d'un nombre x consiste à choisir un bit dans la représentation binaire de x et à le retourner de 0 à 1 ou de 1 à 0.

• Par exemple, forx = 7, la représentation binaire est 111 et nous pouvons choisir n'importe quel bit (y compris les zéros non affichés) et l'inverser. Nous pouvons retourner le premier bit à droite pour obtenir 110, retourner le deuxième bit à droite pour obtenir 101, retourner le cinquième bit à droite (un zéro non significatif) pour obtenir 10111, etc.

Étant donné deux entiers début et objectif, renvoie le minimum nombre de retournements de bits pour convertir le début en objectif.

Exemple 1 :

• Entrée : début = 10, objectif = 7
• Sortie : 3
• Explication : Les représentations binaires de 10 et 7 sont respectivement 1010 et 0111. Nous pouvons convertir 10 en 7 en 3 étapes :
  • Retournez le premier bit en partant de la droite : 1010 -> 1011.
  • Retournez le troisième bit en partant de la droite : 1011 -> 1111.
  • Inversez le quatrième bit en partant de la droite : 1111 -> 0111.
  • On peut montrer que nous ne pouvons pas convertir 10 en 7 en moins de 3 étapes. Par conséquent, nous revenons 3.

Exemple 2 :

• Entrée : début = 3, objectif = 4
• Sortie : 3
• Explication : Les représentations binaires de 3 et 4 sont respectivement 011 et 100. Nous pouvons convertir 3 en 4 en 3 étapes :
  • Retournez le premier bit en partant de la droite : 011 -> 010.
  • Retournez le deuxième bit en partant de la droite : 010 -> 000.
  • Retournez le troisième bit en partant de la droite : 000 -> 100.
  • On peut montrer que nous ne pouvons pas convertir 3 en 4 en moins de 3 étapes. Par conséquent, nous revenons 3.

Contraintes :

• 0 <= début, objectif <= 10⁹

Indice :

1. Si la valeur d'un bit au début et dans l'objectif diffère, alors nous devons inverser ce bit.
2. Envisagez d'utiliser l'opération XOR pour déterminer quels bits nécessitent un peu d'inversion.

Solution :

Nous devons déterminer combien de positions de bits diffèrent entre le début et l'objectif. Ceci peut être facilement réalisé en utilisant l'opération XOR (^), qui renvoie un 1 pour chaque position de bit où les deux nombres diffèrent.

Mesures:

1. Effectuez l'opération XOR entre le début et l'objectif. Le résultat sera un nombre comportant des 1 dans toutes les positions où le départ et l'objectif diffèrent.
2. Comptez combien de 1 sont présents dans la représentation binaire du résultat (c'est-à-dire la distance de Hamming).
3. Le nombre de 1 nous donnera le nombre minimum de retournements de bits nécessaires.

Implémentons cette solution en PHP : 2220. Retournements de bits minimum pour convertir le nombre

  
  
  Explication:



L'opération ^ (XOR) compare chaque bit de début et d'objectif. Si les bits sont différents, le bit correspondant dans le résultat sera 1.
Nous comptons ensuite le nombre de 1 dans le résultat, ce qui donne le nombre de bits différents, c'est-à-dire le nombre de retournements de bits requis.
L'opération & 1 vérifie si le dernier bit est 1, et >>= 1 décale le nombre vers la droite pour traiter le bit suivant.



  
  
  Complexité temporelle :



La complexité temporelle est (O(log N)), où (N) est le plus grand du début ou de l'objectif, car nous vérifions chaque bit du nombre. Dans le pire des cas, nous parcourrons tous les bits d'un entier de 32 bits (puisque PHP 5.6 fonctionne avec des entiers de 32 bits ou de 64 bits selon le système).



  
  
  Sortir:



Pour début = 10 et objectif = 7, le résultat est 3.
Pour début = 3 et objectif = 4, le résultat est 3.


Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!