Dúvida sobre operadores binários.

robgeek
(usa Debian)

Enviado em 11/04/2017 - 01:03h

Boa noite!

Estou estudando sobre operadores binários e vi que o XOR tem uma propriedade interessante. Ele é reversível, ou seja, se A^B=C então C^B=A ou C^A=B. Vi que o mesmo acontece com XAND.

Queria saber se outras propriedades interessantes como essa em outras operações binárias, como OR, AND...

EnzoFerber
(usa FreeBSD)

Enviado em 11/04/2017 - 08:27h

Olá,

Realmente é uma propriedade interessante. Tão interessante que existe uma implementação de listas encadeadas usando-a: https://en.wikipedia.org/wiki/XOR_linked_list.
Já o XAND, também conhecido como XNOR é a negação do XOR, portanto, você consegue a mesma proriedade, só que invertida. https://en.wikipedia.org/wiki/XNOR_gate

Sei que as portas NAND e NOR são funcionalmente completas. O que isso significa é que você pode construir *qualquer* porta lógica a partir de uma combinação dessas portas. Você pode ler mais sobre completude funcional aqui: https://en.wikipedia.org/wiki/Functional_completeness.

Falando um pouco mais rebuscado, um conjunto de operações lógicas é dito funcionalmente completo se, e somente se, através de uma combinação dos elementos do conjunto você consegue expressar todas as tabelas-verdades possíveis. O conjunto A = {AND, NOT} é funcionalmente completo, assim como os conjuntos B = {NAND} e C = {NOR}. Você consegue construir uma CPU completa usando apenas portas NAND, ou apenas portas NOR. Tem inclusive um curso muito interessante chamado "From NAND to Tetris", vale a pena conferir: http://www.nand2tetris.org/

Quanto aos outros operadores, podem ser usados para testar validades de argumentos. Mas aí você precisa estudar lógica formal: http://maude.sip.ucm.es/~miguelpt/papers/flogic.pdf

Já "propriedades" interessantes, são várias. Você pode ler Hacker's Delight - vai achar muita coisa legal: https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685


Enzo Ferber
[]'s

$ indent -kr -i8 src.c



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." 

        - linux/Documentation/CodingStyle - TORVALDS, Linus. 

 

robgeek
(usa Debian)

Enviado em 11/04/2017 - 23:18h

Obrigado por sua resposta, cara!

robgeek
(usa Debian)

Enviado em 28/06/2017 - 16:26h

Boa tarde!

Tenho mais uma dúvida sobre o xor.

Digamos que eu queira realizar a operação xor, mas em três bytes dessa vez, A, B e C:
A ^ B ^ C = X.

Testei algumas vezes e consegui fazer o retorno: X ^ B ^ C = A, por exemplo.
Mas como estou sem tempo de ficar testando indefinidamente resolvi perguntar. Com três bytes é possível retornar em todos os casos, como acontece quando faço com dois?

Obrigado!

removido
(usa Nenhuma)

Enviado em 28/06/2017 - 16:36h

Primeira pergunta: não. Você deveria montar uma tabela-verdade para AND e OR para confirmar.

Segunda: Você não percebeu ainda que está operando com dois operadores. Em três operandos não existe necessariamente uma inversão.

(A^B)^C=X
X^(A^B)=C

A operação ^ é comutativa e associativa.

A^B não muda e pode ser fechada em parêntesis e isolada. Exatamente como D=A^B. Transforma-se em uma variável. Logo:

C^D=X e X^D=C.

A coisa fica um pouco boba.

Dá para fazer por indução a mais variáveis, mas fica complicado. M^N^O^P ....

EDIT:

Não são bytes. São bits. Bytes são 8 bits.

EnzoFerber
(usa FreeBSD)

Enviado em 29/06/2017 - 09:15h

O XOR é bem interessante.
Você sabia que pode fazer swap sem usar variáveis temporárias usando XOR?

Tenta aí. O código usando uma variável temporária é:

int a = 10;

int b = 20;

int temp;



temp = a;

a = b;

b = temp;

 

Como fazer isso sem usar uma variável temporária? XOR.

Enzo Ferber
[]'s

$ indent -kr -i8 src.c



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." 

        - linux/Documentation/CodingStyle - TORVALDS, Linus.