• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

nDray

Problema binário - combinatória

30 mensagens neste tópico

Boas tardes. Queria resolver este problema para optimizar um programa.

Tenho 3 palavras de 2 bits. Quero poder permutá-las entre si o obter os mesmos resultados.

Para as seguintes (todas iguais), quero o resultado 00.

01        10        11
01        10        11
01        10        11
__        __        __
00        00        00

Para todas diferentes, 00 também:

01
10
11
__
00

Para estas quero um resultado diferente de 0!

11        11        01        01        10        10
11        11        01        01        01        10
10        01        10        11        01        11

para

00
00
00

Posso ter um resultado qualquer pois nunca terei isso como argumento!

EDIT: Na verdade, basta uma palavra ser 00 e pode-se logo ignorar.....

Em pouco texto:

Tenho 3 palavras,

- Se forem todas iguais ou todas diferentes, quero zero!

- Se houver duas iguais e uma diferente, quero 1, 10 ou 11....

Tenho XORs, ORs, ANDs e NOTs. Conseguem?  Solução simples?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Se houver duas iguais e uma diferente, quero 1, 10 ou 11....

Não dizes qual é o resultado que tem que dar pelo que não é possivel chegar a solução nenhuma.

Quando é que tem que ser 10, quanto é que tem que ser 11?

Já agora, esses operadores lógicos... são bit-a-bit?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

sim, bit a bit.

Não digo porque me é indiferente! É o que facilitar mais a lógica! E deve ajudar porque isto é uma questão de testar paridades, não estou é a encontrar solução genérica, mas ainda tenho de olhar mais um pouco...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que já tenho uma solução...

Isto é fácil, eu é que não estava a pensar bit a bit!

Acho que esta tabela resolve, mas ainda não testei

000 0
001 1
010 1
011 1
100 1
101 0
110 0
111 0

Acho que cobre o problema todo.... Bem, vou almoçar :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mmm... isto resolve-se com recurso a uma mapa de karnough.

Não tenho comigo a minha sebenta de sistemas digitais :P

Vou ver se resolvo isto a olho.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A tabela que apresentaste é bit a bit com os três inputs?

É que tu dizes 001 : 1 e 010: 1

Então se tiveres:

00

10

01

Vai devolver 11, apesar de serem todos diferentes...

Ah mas tu disseste que 00 não acontecia. Ok

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que já tenho uma solução...

Isto é fácil, eu é que não estava a pensar bit a bit!

Acho que esta tabela resolve, mas ainda não testei

000 0
001 1
010 1
011 1
100 1
101 0
110 0
111 0

Acho que cobre o problema todo.... Bem, vou almoçar :)

000 0
001 1
010 1
011 0 <- aqui tinha 1, é zero
100 1
101 0
110 0
111 0

Cheguei à conclusão final.... Na prática, a situação que quero excluir acontece quando há exactamente dois zeros (bit a bit) em 3 palavras.

|A ( B (+) C ) + A |B |C

resolve.

obrigado pedrotuga e pedrosorio :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Humm...

Afinal não resolve... Estava enganado... Com este, as palavras 11 11 10, por exemplo, retornam 0... Não pode...

Não tenho exactamente 2 zeros e não pode ser esse o único critério... Deste modo não encontro maneira de resolver, bit a bit.... Mas tem de haver solução, certo?

EDIT: Na verdade dá mais jeito usar 00, 01 e 10, e 11 não acontece, mas a lógica seria a mesma, era só inverter....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Z = (&(!(A XOR :P) OR &(!(A XOR C)) OR &(!(B XOR C)))  AND  (&(!(A XOR :)) AND &(!(A XOR C)) AND &(!(B XOR C)))

Tentando explicar:

A XOR B = Faz o XOR entre A e B, bit a bit. Ou seja, cada bit do resultado será 1 se o bit correspondente de A e o bit correspondente de B forem diferentes.

110 XOR 100 = 010

!A = Negação, bit a bit.

!101 = 010

Conjugando !(A XOR B) obtenho algo assim:

!(110 XOR 100) = 101, ou seja, 1 onde os elementos forem iguais. (isto é um XNOR)

&A - and binário aos elementos de A. Só se obtém 1 se os bits forem todos iguais a 1.

Ou seja:

&010 = 0

&111 = 1

A AND B - and bit a bit entre dois números

A OR B - or bit a bit entre dois números

Explicando o que fiz:

Na primeira parte, Z será 1 quando dois elementos forem diferentes.

Na segunda parte, teremos 0 quando os 3 elementos forem iguais.

Fazendo um and entre elas, teremos um 1 quando dois elementos forem diferentes, mas os 3 não forem iguais, ou seja, o pedido.

Repara que a segunda parte só é diferente da primeira dos ORs para os ANDs.

Espero que não esteja confuso. Não tenho a certeza disto..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não me dá jeito fazer operações entre os bits da palavra... nenhum mesmo. fora de questão.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já agora, como é que queres implementar isto? Verilog?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

é para software. C, C++ ou D... indiferente... É para optimizar um problema... Tenho uma solução fácil usando palavras de 3 bits, mas 2 era muito melhor, ainda que com um pouco mais de lógica...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Warrior, podes explicar porque é que usas &(!(A XOR :P), ou melhor, porque é que usas &(!(...)), supostamente &A == &(!A), certo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

z= ((a!=b || a!=c || a!=d) && (a==b || a==c || b==c))

Isto não é válido?

Claro que podes não fazer tantas comparações, criando ifs encadeados, mas sinceramente não me parece que ganhes o que quer que seja nestas optimizações de caca..

pedrosorio:

&000 = 0

&111 = 1

Como é que pode ser igual?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

"&A - and binário aos elementos de A. Só se obtém 1 se os bits forem todos iguais."

Eu nunca dei SD nem nada do género e como tal limitei-me a seguir a tua definição.

Evidentemente que lendo novamente "and binário aos elementos de A" consigo deduzir que apenas será 1 se for 111.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

z= ((a!=b || a!=c || a!=d) && (a==b || a==c || b==c))

Isto não é válido?

Claro que podes não fazer tantas comparações, criando ifs encadeados, mas sinceramente não me parece que ganhes o que quer que seja nestas optimizações de caca..

Ganho porque vou trabalhar centenas de milhar (talvez mais) de vezes sobre bastantes registos, e com o que já tenho posso mesmo crer que poupei muito... Esta ultima não é tanto em velocidade, mais em memória... Usaria registos de 1byte em vez de 2bytes...

E porque a piada é encontrar soluções inteligentes e não if if if if else else if if.....

pedrosorio, &(!A) é diferente de &(!A)... Faz a tabela de verdade, se precisares...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

nDray, se leres a minha mensagem vais perceber que o problema estava no facto de eu ter interpretado que &(A) significava que seria 1 se e só se todos os bits de A fossem iguais.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, é isso!

Mas se reflectires na resposta do Warrior acho que percebes... Ou então sou eu que não estou a dar a devida atenção à discussão... :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Faltava lá um "a 1", de facto tens razão pedrosorio, já corrigi.

nDray: se vais implementar isto em C/C++, devias ponderar em vez de estares a escrever o código com menos uma ou duas comparações escrever em ASM "embebido" (falta-me o termo correcto) no resto do teu código.

Isto claro, se não for mesmo possível optimizar de outra forma significativa algoritmicamente.

Como side note: um processador actual consegue fazer cerca de 100.000.000 de operações em menos de um segundo, portanto centenas de milhar não é muito.

Caso estejas a pensar ler os dados de um ficheiro, por exemplo, o tempo que perdes a ler/escrever os dados é bastante maior do que o que levas a processar.

Por exemplo, ler 1.000.000 de inteiros em C++ usando scanf() é cerca de 10x mais rápido do que usando cin.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

eu sei... costumo usar a stdio mesmo em c++...

Cheguei à conclusão de que não compensa pelo simples facto de a solução aumentar muito a complexidade....

grato pelo esforço :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ASM "embebido" (falta-me o termo correcto)

In-line Assembly.
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Volto a achar que existe uma solução simples, escolhendo estados pelo código de gray....

Usar a mesma ideia que exprimi no texto curto do primeiro post, mas codificando os 3 estados possíveis de cada palavra com 00, 01, 11  ou então  00, 10, 11, é indiferente...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Esta expressão resolve o teu problema:

(!(A ^ B) ^ C) && (A & B & C)

!A    = Negação bit-a-bit

A^B = A XOR B

&&  = And Logico

A&B = And bit-a-bit

A primeira parte verifica se é composto por dois números iguais. A distributividade do ^ assim o permite. (Dá 0 se forem os 3 iguais).

Cumprimentos

Falso. Daria zero (A ^ B) & (B ^ C).

Acho que isto serve:

~A & (A^B | C)

Tenho de testar, ainda...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Hey. Eu depois apaguei porque a segunda parte não faz sentido.

Mas isto está correcto:

(!(A ^ B) ^ C)

Verifica se é composto por dois números iguais. A distributividade do ^ assim o permite. (Dá 0 se forem os 3 iguais).

Agora só falta verificar se todos os números NÂO são diferentes, porque essa expressão deixa passar isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas esse ! Não me serve.. Isso não representa nada, bit a bit.... E não me ajuda porque preciso que seja bit a bit... A outra solução que dei também não funciona....

EDIT:

Eu acabo sempre a pensar que só com 2 bits é mesmo impossível porque não há tabela de verdade a 3 bits que resolva o problema.... Mas até alguém que sabe do assunto me disser isso ponho-me a pensar numa forma...........

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora