domingo, 26 de fevereiro de 2012

(Matematica) Explicação de XOR

XOR é um operador que utiliza como base números binários e a verificação Numero a Numero deles usando a lógica booleana disjunção exclusiva que é baseada na seguinte regra

Números iguais = 0
1 + 1 = 0
0 + 0 = 0

Números diferentes = 1
1 + 0 = 1
0 + 1 = 0

É parecido com aquele sistema que aprendendo na escola

++ = +
-- =  +

-+ = -
+- = -


Vou explicar com base no algorítimo XOR SWAP.. XOR Swap que é um algorítimo de troca de valores na memória. Basicamente quando tenho o valor 10 e o valor 5 (exemplo) o operador xor irá interpreta-los utilizando a lógica OU EXCLUSIVO (dai vem o termo XOR "exclusive or" receio)


Em XOR Swap fizemos
5 ^ 10 -> passo 1 
(5 ^ 10) ^ 5 -> passo 2
((5 ^ 10) ^ 5) ^ 10 -> passo 3
(explicarei como XOR fez isto)

Que resultando dará:
10,5 (antes era 5,10 lembra?) -> INVERTEMOS OS NÚMEROS NA MEMÓRIA 

Mas como ocorre está "mágica"? .. Agora vou explicar

A operação tem como base números binários e a comparação número a número
10 = 1010 em binário
5 = 101 e, binário
_______________________

Sendo assim vamos aos passos

PASSO 1:
Comparando número-número (eles estão na vertical em binário, preste atenção)
  1 = 1 (quando não há valores o valor é 0 logo 0 com 1 é 1)
10 = 1 
01 = 1
10 = 1
(a coluna a esquerda é o número cinco em binário a coluna da direita é o dez em binário, são 2 números binários na verical) 1111 foi o resultado

Importante: 1111 em binário é 15 por este motivo (5 ^ 10) é 15

Resultado:
5 ^ 10 logo é: 1111 sendo assim vamos para o passo 2

PASSO 2
Então fizemos (5 ^ 10) ^ 5 (sendo que 5 é 101 em bin e (5 ^ 10)  é 1111)

1   = 1  (true + false é true)
11 = 0 (true + true é false)
10 = 1  (true + false é true)
11 = 0 (true  + true é false)

(primeira coluna é o resultado do passo 1 a segunda coluna é o 5 em binário)

Resultado:
Logo ((5 ^ 10) ^ 5) é: 1010 
Importante: 1010 em bínario é 10 logo por isto  ((5 ^ 10) ^ 5) dá como resultado 10

PASSO 3
Agora vamos fazer
((5 ^ 10) ^ 5) ^ 10 

Levando em conta que (5 ^ 10) ^ 5) é 1010 em binário (10 em decimal) . Nesta etapa tem um detalhe. 

Se for ao pé da letra
(5 ^ 10) ^ 5) ^10 dará zero
Pois:
11 = 0
00 = 0
11 = 0
00 = 0

Fail? Quase.
O que acontece é que na verdade não é (5 ^ 10) ^ 5) ^10 mas sim (5 ^ 10) ^ 5) ^ VALOR DO PRIMEIRO PASSO
Porque? Porque quando fizemos o xor swap a variável X irá assumir outro valor no passo 1. LEMBRE-SE

x = 5
y = 10

x ^= y RESULTADO 15 (1 passo)
y ^= x RESULTADO 10 (2 passo)
x ^= y -> A VARIAVEL X TEM VALOR 15 NÃO 10. Logo é 15 ^ 10 

É um pega ratão e tanto, mas mesmo assim

15 = 1111 em binário
10 = 1010 em binário

11 = 0
10 = 1
11 = 0
10 = 1

0101 = 5 PERCEBERAM? X assumiu valor 5 (3 passo) e Y ficou com valor 10 (2 passo)

Assim efetuando o troque de dar swap nos valores.
XOR é usado em computador, como principal ferramenta para portas lógicas, verdadeiro e falso. Muito tempo andei procurando sobre XOR, raramente você encontra alguém explicar como realmente é feito este cálculo, isto porque 90% das pessoas apenas sabem como teoricamente funciona, mas dando para fazer um calculo, ela não faz.

Abraços

2 comentários:

  1. Uai meu parceiro. Seu banner sempre esteve adicionado ao meu blog nunca o retirei. Olhe no Lado direito em parceiros :)

    Peço que adicione meu banner novamente ao seu site,Obrigado , Abçs

    www.kelvinsantiago.com.br

    ResponderExcluir
  2. Bruno não entendo amigo, seu banner está funcionando e redirecionando corretamente, e este codigo seu está criptografado e não sei a função que ele faz :) . Valeu abç

    www.kelvinsantiago.com.br

    ResponderExcluir