Passen Sie die Binärdarstellungslängen zweier Zahlen an, sodass sie gleich sind, und führen Sie dann eine XOR-Operation durch

XOR oder exklusives ODER ist eine boolesche Logikoperation, die zum Generieren von Paritätsbits für Fehlerprüfung, Fehlertoleranz usw. verwendet wird. Zur Darstellung dieser Operation werden verschiedene Symbole verwendet: ^, ⊕, ⊻ usw.

XOR-Logik

Die XOR-Operation ist nur wahr, wenn die beiden Parameter unterschiedlich sind. Mit anderen Worten, das XOR derselben Bits ist 0 und das XOR verschiedener Bits ist 1.

Gleiche Teile -

0^0=0

1^1=0

Verschiedene Bits −

0^1=1

1^0 = 1

Problemstellung

Bestimmen Sie für zwei gegebene Zahlen a und b deren XOR, nachdem Sie die Längen ihrer binären Darstellungen gleich gemacht haben.

Tipp − Durch Hinzufügen einer abschließenden Null nach der kleineren Zahl wird die Binärdarstellung gleich.

Beispiel

Eintreten -

a = 10, b = 5

Ausgabe-

0

Anleitung

Die binäre Darstellung von 10 ist 1010 und die binäre Darstellung von 5 ist 101.

Fügen Sie die nachgestellte Null zu 5 hinzu, um 1010 zu erhalten.

Daher ist das XOR-Ergebnis von 1010^1010 0.

Daher Ausgabe.

Eintreten -

a = 15, b = 8

Ausgabe −

7

Anleitung -

Die binäre Darstellung von 15 ist 1111 und die binäre Darstellung von 8 ist 1000.

Da beide Binärdarstellungen gleich lang sind, müssen keine nachgestellten Nullen hinzugefügt werden.

Das XOR-Ergebnis von

1111 ^ 1000 ist 0111, was in Dezimalschreibweise 7 ist. Daher beträgt die Ausgabe 7.

Eintreten -

a = 15, b = 3

Ausgabe −

7

Anleitung -

Die binäre Darstellung von 15 ist 1111. Die binäre Darstellung von 3 ist 11. Die binäre Darstellung von 3 mit einer nachgestellten Null wird zu 1100.

Das XOR-Ergebnis von 1111^1100 ist 0011.

0011 ist 3 in Dezimaldarstellung. Daher wird das Ergebnis ausgegeben.

Methode

• Zählen Sie die Anzahl der Ziffern in zwei Zahlen.

• Die Anzahl der Ziffern kann berechnet werden, indem man die Zahl nach rechts verschiebt, bis sie Null wird, und zählt, wie oft die Schleife ausgeführt wird. Das Verschieben einer Zahl um eine Stelle nach rechts entspricht einer Division durch zwei.

• Wenn die kleinere Zahl weniger Ziffern hat, führen Sie die Linksverschiebung wie folgt durch: kleinere_Zahl

• XOR zwei Zahlen, um die Antwort zu erhalten und sie auszudrucken.

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.

Beispiel

Unten finden Sie ein C++-Programm zur Berechnung des XOR-Werts zweier Zahlen, nachdem ihre binären Darstellungen in der Länge gleich gemacht wurden.

#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;
}

Ausgabe

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

Analyse

Zeitkomplexität - O(log n) [Logarithmus]

Aufgrund der while-Schleife in der Zählfunktion ist die Zeitkomplexität logarithmisch.

Da diese Zahl durch zwei geteilt wird, bis sie Null wird, beträgt die Komplexität log n zur Basis 2.

Raumkomplexität - O(1) [Konstante]

Die Speicherplatzkomplexität ist konstant, da im Programm kein zusätzlicher Speicherplatz verwendet wird.

Fazit

In diesem Artikel haben wir das Problem der Berechnung des XOR zweier Zahlen besprochen, nachdem ihre binären Darstellungen in der Länge gleich gemacht wurden.

Wir haben das Konzept von XOR besprochen und anschließend Beispiele und Methoden erläutert. Diese Methode verwendet nachgestellte Nullen, um die Anzahl der Bits in der Binärdarstellung auszugleichen. Wir haben auch Pseudocode und ein C++-Programm für das Problem gesehen.

Das obige ist der detaillierte Inhalt vonPassen Sie die Binärdarstellungslängen zweier Zahlen an, sodass sie gleich sind, und führen Sie dann eine XOR-Operation durch. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!