Laraskan panjang perwakilan binari dua nombor menjadi sama dan kemudian lakukan operasi XOR

XOR, atau eksklusif OR, ialah operasi logik Boolean yang digunakan untuk menjana bit pariti untuk semakan ralat, toleransi kesalahan, dsb. Pelbagai simbol digunakan untuk mewakili operasi ini: ^, ⊕, ⊻, dsb.

Logik XOR

Operasi XOR adalah benar hanya jika kedua-dua parameter berbeza. Dengan kata lain, XOR bagi bit yang sama ialah 0, dan XOR bagi bit yang berbeza ialah 1.

Bit yang sama -

0^0=0

1^1=0

Bit yang berbeza −

0^1=1

1^0 = 1

Pernyataan Masalah

Diberi dua nombor a dan b, cari XORnya selepas membuat panjang perwakilan binarinya sama.

Petua − Dengan menambah sifar mengekor selepas nombor yang lebih kecil, perwakilan binari akan menjadi sama.

Contoh

Masuk -

a = 10, b = 5

Output-

0

Arahan

Perwakilan binari 10 ialah 1010 dan perwakilan binari 5 ialah 101.

Tambah sifar di belakang kepada 5 untuk mendapatkan 1010.

Oleh itu, keputusan XOR bagi 1010^1010 ialah 0.

Oleh itu, output.

Masuk -

a = 15, b = 8

Output −

7

Arahan -

Perwakilan binari 15 ialah 1111 dan perwakilan binari 8 ialah 1000.

Memandangkan kedua-dua perwakilan binari adalah sama panjang, tidak perlu menambah sifar mengekor.

Hasil XOR bagi

1111 ^ 1000 ialah 0111, iaitu 7 dalam tatatanda perpuluhan. Oleh itu, keluarannya ialah 7.

Masuk -

a = 15, b = 3

Output −

7

Arahan -

Perwakilan perduaan bagi 15 ialah 1111. Perwakilan perduaan bagi 3 ialah 11. Perwakilan perduaan bagi 3, dengan sifar mengekor, menjadi 1100.

Hasil XOR bagi 1111^1100 ialah 0011.

0011 ialah 3 dalam perwakilan perpuluhan. Oleh itu, hasilnya adalah output.

Kaedah

• Kira bilangan digit dalam dua nombor.

• Bilangan digit boleh dikira dengan mengalihkan nombor ke kanan sehingga menjadi sifar, dan mengira bilangan kali gelung dilaksanakan. Mengalihkan nombor ke kanan sebanyak 1 tempat adalah bersamaan dengan membahagikannya dengan 2.

• Jika nombor yang lebih kecil mempunyai lebih sedikit digit, lakukan anjakan kiri seperti berikut: smaller_number

• XOR dua nombor untuk mendapatkan jawapan dan mencetaknya.

pseudokod

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.

Contoh

Di bawah ialah program C++ untuk mengira nilai XOR dua nombor selepas membuat perwakilan binarinya sama panjang.

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

Output

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

Analisis

Kerumitan masa - O(log n) [logaritma]

Disebabkan gelung while dalam fungsi kiraan, kerumitan masa adalah logaritma.

Oleh kerana nombor ini dibahagikan dengan dua sehingga menjadi sifar, kerumitan menjadi log n asas 2.

Kerumitan Angkasa - O(1) [Malar]

Kerumitan ruang adalah malar kerana tiada ruang tambahan digunakan dalam program.

Kesimpulan

Dalam artikel ini, kami membincangkan masalah pengiraan XOR dua nombor selepas membuat perwakilan binarinya sama panjang.

Kami membincangkan konsep XOR dan kemudian menerangkan contoh dan kaedah. Kaedah ini menggunakan sifar mengekor untuk menyamakan bilangan bit dalam perwakilan binari. Kami juga melihat pseudokod dan program C++ untuk masalah itu.

Atas ialah kandungan terperinci Laraskan panjang perwakilan binari dua nombor menjadi sama dan kemudian lakukan operasi XOR. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!