Vérifiez si deux nombres donnés peuvent être rendus égaux en changeant 1 ou 2 bits en C++

Dans le domaine de la programmation informatique, de nombreuses opérations tournent autour de valeurs numériques. Dans certains cas, nous devrons peut-être déterminer si deux nombres peuvent être rendus égaux en modifiant quelques bits. Même si ce problème peut présenter des défis, la bonne stratégie mènera à une solution efficace.

Grammaire

Pour construire une base solide pour une compréhension approfondie de l'algorithme, familiarisons-nous d'abord avec la syntaxe utilisée dans le codage ultérieur en utilisant cette approche spécifique.

bool checkEquality(int num1, int num2);

Générez une réponse booléenne en utilisant la fonction checkEquality pour déterminer si les deux entiers donnés num1 et num2 peuvent être rendus égaux en changeant seulement un ou deux bits.

Algorithme

Voici une présentation étape par étape de notre algorithme :

• Déterminez le résultat XOR de num1 et num2 et attribuez la sortie à une nouvelle variable xorResult.

• Utilisez un algorithme pour compter le nombre de bits définis dans xorResult et attribuez le résultat à une variable appelée setBitCount.

• Pour que l'opération réussisse, setBitCount ne peut pas dépasser 2. Dans ce cas, notre fonction renverra un vrai résultat. Si ce seuil spécifié est dépassé, nous pouvons conclure que notre sortie doit être fausse.

• Maintenant que nous avons l’algorithme, examinons au moins deux manières différentes de résoudre ce problème.

Méthode 1 : Opération sur bits

Dans cette méthode, nous utiliserons des opérations sur les bits pour vérifier si les nombres peuvent être rendus égaux.

Exemple

#include <iostream>

bool checkEquality(int num1, int num2) {
   int xorResult = num1 ^ num2;
   int bitCheck = xorResult & (xorResult - 1);
   return (bitCheck == 0);
}

int main() {
   int number1, number2;
   std::cout << "Enter the first number: ";
   std::cin >> number1;
   std::cout << "Enter the second number: ";
   std::cin >> number2;
    
   bool result = checkEquality(number1, number2);
   if (result) {
      std::cout << "It is possible to make the numbers equal by changing only one or two bits." << std::endl;
   } else {
      std::cout << "It is not possible to make the numbers equal by changing only one or two bits." << std::endl;
   }  
   return 0;
}

Sortie

Enter the first number: Enter the second number: It is not possible to make the numbers equal by changing only one or two bits.

Explication

En modifiant la valeur d'un ou deux des bits, le code C++ effectue une vérification simple pour déterminer si un alignement parfait entre les deux valeurs fournies peut être établi lors du traitement. Pour atteindre cet objectif, une partie importante du code consiste à définir une fonction spéciale appelée « checkEquality ». L'utilisation de cette fonction personnalisée nécessite de fournir deux variables entières en entrée. Le type de sortie de cette fonction particulière utilise la logique booléenne afin que l'utilisateur puisse facilement obtenir un résultat indiquant si les arguments fournis à la fonction lors de l'exécution sont suffisants pour un alignement numérique parfait.

À des fins de calcul, ce programme utilise l'algorithme XOR pour comparer les entrées entières ci-dessus via la méthode checkEquality. Ensuite, le résultat automatiquement stocké est capturé dans la variable "xorResult". L'élément clé de l'étape suivante est de calculer le résultat intermédiaire ET au niveau du bit entre xorResult et XORResult - 1. A ce stade, lorsque la valeur de retour est "0", l'hypothèse de la variable bitCheck devient nécessaire. Parce que cela indique qu'une condition nécessaire est remplie, nous pouvons supposer qu'un ou deux bits de l'entrée entière doivent changer pour satisfaire la demande faite par la fonction checkEquality. Une fois terminé, le programme demande à l'utilisateur une saisie, avant de transmettre les paramètres dans la méthode checkEquality comme étape de calcul finale. Une fois le processus terminé, un message de sortie indique la présence/absence des changements de niveau de bit requis et un message correspondant est affiché dans la sortie de la console. Cette implémentation montre un excellent exemple de manipulation au niveau du bit et d'utilisation de XOR, à partir de C++.

Méthode 2 : Méthode de distance de Hamming

Dans cette méthode, nous utiliserons la notion de distance de Hamming pour résoudre le problème.

Exemple

#include <iostream>

int countSetBits(int num) {
   int count = 0;
   while (num) {
      num &= (num - 1);
      count++;
   }
   return count;
}

bool checkEquality(int num1, int num2) {
   int xorResult = num1 ^ num2;
   int setBitCount = countSetBits(xorResult);
   return (setBitCount <= 2);
}

int main() {
   int number1, number2;
   std::cout << "Enter the first number: ";
   std::cin >> number1;
   std::cout << "Enter the second number: ";
   std::cin >> number2;
    
   bool result = checkEquality(number1, number2);
   if (result) {
      std::cout << "It is possible to make the numbers equal by changing only one or two bits." << std::endl;
   } else {
      std::cout << "It is not possible to make the numbers equal by changing only one or two bits." << std::endl;
   }   
   return 0;
}

Sortie

Enter the first number: Enter the second number: It is not possible to make the numbers equal by changing only one or two bits.

Explication

Dans cet exemple, nous fournissons un programme C++ conçu pour déterminer si nous pouvons apporter des modifications à un ou éventuellement deux bits pour rendre deux nombres différents équivalents. De plus, il existe une fonction appelée « countSetBits » qui utilise l'algorithme de Kemighan pour déterminer combien de bits définis sont présents dans une valeur entière.

Dans la fonction checkEquality, le code calcule le OU exclusif des deux nombres saisis et stocke le résultat dans xorResult. L'instruction précédente déclenche la fonction countSetBits pour déterminer le nombre de bits définis dans xorResult, qui est ensuite accumulé dans setBitCount. Chaque fois que setBitCount est déterminé comme étant égal à deux ou moins, cela signifie que seuls un ou deux bits doivent être modifiés pour atteindre l'équilibre, ce qui fait que la fonction renvoie vrai. Sinon, retournez false.

Dans la fonction principale, le programme invite l'utilisateur à saisir deux nombres. Il appelle ensuite la fonction checkEquality en utilisant le numéro fourni par l'utilisateur et stocke le résultat. Enfin, en fonction de la valeur du résultat, le programme imprime un message approprié indiquant s'il est possible de rendre les nombres égaux en changeant un ou deux bits.

Ce code fournit une implémentation claire du problème, en utilisant les opérations XOR et l'algorithme de Kernighan pour calculer efficacement les bits définis.

Conclusion

Notre article aborde le problème de déterminer si deux nombres donnés peuvent être égaux en ne changeant qu'un ou deux bits. Pour résoudre ce problème, nous proposons deux méthodes efficaces : la méthode des opérations sur bits et la méthode de la distance de Hamming. Les deux méthodes offrent des solutions efficaces. Nous fournissons également de vrais exemples de code exécutable basés sur ces méthodes. En comprenant et en mettant en œuvre ces méthodes, vous pouvez vérifier efficacement si deux nombres peuvent être rendus égaux en modifiant quelques bits.

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!