Explique o uso do xor para encontrar dois números inteiros não duplicados em uma matriz
Dado[1,1,4,5,5,6]
nós podemos encontrar4
e6
para ser os números inteiros não repetitivos.
Existe umsolução usandoXOR
.
Aqui está o algoritmo proposto pelo autor:
#include <stdio.h>
#include <stdlib.h>
/* This finction sets the values of *x and *y to nonr-epeating
elements in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)
{
int xor = arr[0]; /* Will hold xor of all elements */
int set_bit_no; /* Will have only single set bit of xor */
int i;
*x = 0;
*y = 0;
/* Get the xor of all elements */
for(i = 1; i < n; i++)
xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor & ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i < n; i++)
{
if(arr[i] & set_bit_no)
*x = *x ^ arr[i]; /*XOR of first set */
else
*y = *y ^ arr[i]; /*XOR of second set*/
}
}
Estou confuso quanto ao que se segue depois4^6
. Estou confuso como oset_bit_no
funciona (incluindo a motivação) e o que for depois disso.
Alguém pode tentar explicá-lo da maneira mais clara em inglês? Obrigado.