Ajustez les longueurs de représentation binaire de deux nombres pour qu'elles soient égales, puis effectuez une opération XOR

XOR, ou OU exclusif, est une opération logique booléenne utilisée pour générer des bits de parité pour la vérification des erreurs, la tolérance aux pannes, etc. Différents symboles sont utilisés pour représenter cette opération : ^, ⊕, ⊻, etc.

Logique XOR

L'opération XOR n'est vraie que si les deux paramètres sont différents. En d’autres termes, le XOR des mêmes bits est 0 et le XOR des différents bits est 1.

Mêmes morceaux -

0^0=0

1^1=0

Différents morceaux −

0^1=1

1^0 = 1

Énoncé du problème

Étant donné deux nombres a et b, trouvez leur XOR après avoir égalisé les longueurs de leurs représentations binaires.

Astuce - En ajoutant un zéro final après le plus petit nombre, la représentation binaire deviendra égale.

Exemple

Entrez -

a = 10, b = 5

Sortie-

0

Instructions

La représentation binaire de 10 est 1010 et la représentation binaire de 5 est 101.

Ajoutez le zéro final à 5 ​​pour obtenir 1010.

Par conséquent, le résultat XOR de 1010^1010 est 0.

Par conséquent, sortie.

Entrez -

a = 15, b = 8

Sortie −

7

Instructions -

La représentation binaire de 15 est 1111 et la représentation binaire de 8 est 1000.

Étant donné que les deux représentations binaires sont de longueur égale, il n'est pas nécessaire d'ajouter des zéros à droite.

Le résultat XOR de

1111 ^ 1000 est 0111, soit 7 en notation décimale. Le résultat est donc 7.

Entrez -

a = 15, b = 3

Sortie −

7

Instructions -

La représentation binaire de 15 est 1111. La représentation binaire de 3 est 11. La représentation binaire de 3, avec un zéro final, devient 1100.

Le résultat XOR de 1111^1100 est 0011.

0011 vaut 3 en représentation décimale. Par conséquent, le résultat est affiché.

Méthode

• Comptez le nombre de chiffres dans deux nombres.

• Le nombre de chiffres peut être calculé en décalant le nombre vers la droite jusqu'à ce qu'il devienne zéro et en comptant le nombre de fois que la boucle est exécutée. Décaler un nombre d’une case vers la droite équivaut à le diviser par 2.

• Si le plus petit nombre a moins de chiffres, effectuez le décalage vers la gauche comme suit : plus petit_numéro

• XOR deux nombres pour obtenir la réponse et l'imprimer.

pseudocode

main()
Initialize a -> 15  and  b -> 3.
Function call find_xor(a,b);

find_xor(int a, int b):
c -> minimum of a and b.
d -> maximum of a and b.
count_c -> bit_count(c)
count_d ->bit_count(d)
If count_c < cound_d, then:
c -> c << (count_d - count_c)
Return c XOR d.

bit_count(int x):
count -> 0
while(x != 0):
	Increase the count by one.
	Right shift x by 1, i.e., divide it by 2.
Return x.

Exemple

Vous trouverez ci-dessous un programme C++ permettant de calculer la valeur XOR de deux nombres après avoir rendu leurs représentations binaires égales en longueur.

#include <bits/stdc++.h>
using namespace std;
// Function to count the number of bits in binary representation
// of an integer
int bit_count(int x){
   //Initialize count as zero
   int count = 0;
   //Count the bits till x becomes zero.
   while (x)	{
      //Incrementing the count
	  count++;
      // right shift x by 1
      // i.e, divide by 2
      x = x>>1;
   }
   return count;
}
//Function to find the XOR of two numbers. Trailing zeros are added to the number having a lesser number of bits to make the bits in both numbers equal.
int find_xor(int a, int b){
   //Store the minimum and maximum of both the numbers
   int c = min(a,b);
   int d = max(a,b);
   //Store the number of bits in both numbers.
   int count_c = bit_count(c);
   int count_d = bit_count(d);
   //If the number of bits in c is less, left shift if by the number of exceeding bits.
   if (count_c < count_d){
      c = c << ( count_d - count_c);
   }
   return (c^d);
}
//Driver code
int main(){
   //Initialize a and b.
   int a = 15, b = 3;
   cout << "a = 15, b = 3" << endl;
   //Store the XOR of both the numbers after required computations
   //Function call
   int ans = find_xor(a,b);
   //Print the final result
   cout << "XOR of a and b: "<<ans<<endl;
   return 0;
}

Sortie

a = 15, b = 3
XOR of a and b: 3

Analyse

Complexité temporelle - O(log n) [logarithme]

En raison de la boucle while dans la fonction count, la complexité temporelle est logarithmique.

Puisque ce nombre est divisé par deux jusqu'à devenir zéro, la complexité devient log n base 2.

Complexité spatiale - O(1) [Constante]

La complexité de l'espace est constante car aucun espace supplémentaire n'est utilisé dans le programme.

Conclusion

Dans cet article, nous avons discuté du problème du calcul du XOR de deux nombres après avoir rendu leurs représentations binaires de longueur égale.

Nous avons discuté du concept de XOR puis expliqué des exemples et des méthodes. Cette méthode utilise des zéros à droite pour égaliser le nombre de bits dans la représentation binaire. Nous avons également vu du pseudocode et un programme C++ pour le problème.

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!