O XOR (^) é um tipo de disjunção lógica binária que resulta no valor true se exatamente uns dos seus operandos tem o valor true. O XOR goza das seguintes propriedades:
- A ^ B = B ^ A (Comutatividade)
- (A ^ B)^ C = A^ (B^ C) (Associatividade)
- A^0 = A (Elemento Neutro)
- A^A = 0 (Elemento Inverso)
O XOR é importante por vários motivos:
- Em algumas arquiteturas de computadores, para armazenar 0 em um registrador é mais eficiente realizar a operação XOR com o valor do próprio registrador do que carregar e armazenar o valor zero no registrador.
- O XOR foi um grande desafio para a área de redes neurais. O XOR foi a primeiro exemplo de função que não é linearmente separável. Isso representa que o XOR não pode ser aprendido por um único neurônio artificial e requer uma rede neural multicamada. A área de redes neurais passou um grande tempo para se recuperar desse baque (1969-1982). O problema só foi resolvido como o desenvolvimento de algoritmo de aprendizagem para redes neurais multicamadas.
- O XOR é utilizado em sistemas RAID para guardar informações de paridade. As informações de paridade são utilizadas para detecção de erros e correção.
- O XOR pode ser utilizado para detectar overflow em operações aritméticas com números binários com sinal.
- O XOR pode ser utilizado também para trocar duas variáveis sem a utilização de variáveis auxiliares.
Vamos tentar entender a importância do XOR analisando os seguintes problemas:
Problema 1 100 pessoas são postas em uma fila e cada uma delas recebe um chapéu, que pode ser preto ou branco. Cada pessoa só consegue ver os chapéus das pessoas que estão a sua frente. É pedido que cada uma delas tente adivinhar a cor do seu chapéu. Cada pessoa pode dizer uma cor em voz alta para que todas as pessoas da fila ouçam. A ordem das perguntas na fila é da última pessoa para a primeira. Qual o máximo número de acertos que se pode garantir, dado que as pessoas podem combinar uma estratégia antes de recebê-los. (Problema extraído da revista Eureka n° 31, 2010)
Podemos facilmente conseguir 50 acertos. Basta dividir as pessoas em pares: (100,99), (98, 97),...(2, 1) e assim o maior número de cada par falar a cor da pessoa da frente. Que apenas precisa repeti-lo, para garantir 1 acerto por par. Mas utilizando a informação de paridade que pode ser obtida aplicado o XOR, podemos conseguir 99 acertos da seguinte maneira. A última pessoa calcula a paridade de todas as 99 pessoas que estão a sua frente se a quantidade for par, ela fala BRANCO e se for ímpar, ela fala PRETO. A próxima pessoa calcula a paridade das pessoas que estão a sua frente, se paridade calculada for igual a paridade calculada pela pessoa antes dela na fila então o seu chapéu é BRANCO, caso contrário, o seu chapéu será PRETO. Ela sempre fala a paridade calculada por ela.
Vamos considerar o seguinte exemplo:
5
|
4
|
3
|
2
|
1
|
0
|
1
|
1
|
0
|
1
|
1. A última pessoa (pessoa 5) calcula a paridade dos chapéus visíveis por ele. A quantidade é ímpar então ele fala PRETO.
2. A próxima pessoa (pessoa 4) calcula a paridade dos chapéus visíveis por ele. A quantidade é par e quantidade calculada pela pessoa anterior foi ímpar(Ela disse PRETO). Logo, o seu chapéu é PRETO. Ela fala BRANCO.
3. A próxima pessoa (pessoa 3) calcula a paridade dos chapéus visíveis por ele. A quantidade é ímpar e quantidade calcula pela pessoa anterior foi par (Ela disse BRANCO) então o seu chapéu é PRETO.
Problema 2 O algoritmo de troca de valores de duas variáveis utiliza uma variável auxiliar para realizar a operação da seguinte maneira:
temp = a
a = b
b = temp
Podemos utilizar o XOR para realizar esta operação sem precisar de uma variável auxiliar.
troca_xor(a,b)
a = a^ b (1)
b = a^ b (2)
a = a^ b (3)
Na primeira linha, temos que a = a ^ b. Substituindo o valor de a (1) na equação (2) , temos:
b = a^ b^ b
b = a^ (b^ b) Associatividade
b = a^ 0 Elemento Inverso
b = a Elemento Neutro
Substituindo o valor de a (1) e b(2) na equação (3), temos:
a = a^ b
a = a^ b^ a (Comutatividade)
a = a^ a^ b (Associatividade)
a = (a ^ a)^ b Elemento Inverso
a = 0^ b Elemento Neutro
a = b
Problema 3 Um vetor com n-1 inteiros armazena valores [1..n]. Somente um valor está faltando, descubra qual é o número que está faltando.
Estratégia 1: Utilize um vetor marc para guardar os valores que estão no vetor.
cin >> n;
int vet[n-1];
int marc[n];
memset(marc,0,sizeof(marc));
for(i=0;i<n-1;i++){
cin >> vet[i] ;
marc[vet[i]-1] = 1;
}
for(i=0;i<n;i++)
if(marc[i]==0)
cout << "Valor faltando: " << i+1 << endl;
Complexidade de espaço extra: O(n)
Estratégia 2: Calcula a soma de todos os números entre 1 e n e soma o valor de todos os valores que estão no vetor e depois fazer a diferença.
int n,i;
int soma,total;
cin >> n;
int vet[n-1];
total = ((1+n)*n)/2;
soma = 0;
for(i=0;i<n-1;i++){
cin >> vet[i] ;
soma += vet[i];
}
cout << "Valor faltando: " << total - soma << endl;
Complexidade de espaço extra = O(1)
Problema: Pode ocorrer overflow no cálculo da soma e do total.
Estratégia 3:
int n,i;
int total;
cin >> n;
int vet[n-1];
total = 0;
for(i=1;i<=n;i++)
total ^= i;
for(i=0;i<n-1;i++){
cin >> vet[i] ;
total ^= vet[i];
}
cout << "Valor faltando: " << total << endl;
Entrada
n=3, v = {2,1}
total = 1^ 2^ 3
total = total ^ v[0] = 1^ 2^ 3^ 2 = 1 ^ 3
total = total ^ v[1] = 1^ 3^ 1 = 3
Valor que está faltando : 3
Problema 4 Alice e Bob estão em ilhas separadas. Bob está doente, e Alice tem o medicamento. Eva tem um barco e uma caixa que pode ser bloqueado. Ela está disposta a transportar objetos entre Alice e Bob, mas apenas na caixa, e se a caixa estiver aberta, ela vai roubar o que está dentro. Se Alice e Bob tem cadeados e chaves de tal forma que a sua própria chave só abre o seu próprio cadeado, como Alice envia Bob o medicamento de forma que Eva não vai roubá-lo? e o que precisamos assumir para que esse transporte aconteça?
1° Alice coloca o medicamento na caixa e coloca o seu cadeado.
2° Eva leva a caixa para Bob
3° Bob coloca seu cadeado junto com o cadeado de Alice
4° Eva traz a caixa de volta para Alice
5° Alice retira seu cadeado, evidentemente 'deixando' o cadeado de Bob pois ela não possui a chave
6° Eva leva a caixa para Bob
7° Bob agora pode abrir a caixa e retirar o seu medicamento
Problema 5 Alice e Bob novamente estão em ilhas separadas. Alice quer enviar um inteiro de 32 bits em segredo para Bob. Ela pode enviar um inteiro de 32 bits para Bob atráves de Eva. Eva pode ver o inteiro que ela está levando! Como Bob pode enviar para Alice esse número sem que Eva descubra que número é esse?
Dica: Alice e Bob podem utilizar o operador binário XOR.
Solução:
Seja A um número secreto escolhido por Alice e B um número secreto escolhido por Bob.
Seja X o número que Alice quer enviar em segredo para Bob.
Solução:
Seja A um número secreto escolhido por Alice e B um número secreto escolhido por Bob.
Seja X o número que Alice quer enviar em segredo para Bob.
1° Alice envia para Bob X ^ A .
2° Bob envia X^A ^B
3° Alice envia para BOB X^A ^B ^A
4° Bob descobre o número enviado aplicando X ^A ^B^A^B
Desafio Um vetor com n+1 inteiros armazena valores [1..n]. Somente um valor está duplicado, descubra qual é o número que está duplicado usando XOR.
3 comentários:
Very Informative...
Very Informative...
شركة مكافحة حشرات بالاحساء
شركة مكافحة حشرات بالخبر
Postar um comentário