Operation binaire

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour ! J'implore votre aide face a un probleme d'operation binaire ! Je me trouve avec differents nombre et j'aimerai savoir s'il est possible de faire ca :

On a des nombres tel :

0011010100

0010010000

0001000101

Et j'aimerais le resultat : 0000000001

Voilà voila :)

Édité par Coyote

+0 -0

C'est vague comme question, ou plutôt c'est tellement précis et la réponse tellement évidente, que je ne suis pas sûr de comprendre ce que tu veux… :-°

L'opérateur nécessaire pour ce calcul saute aux yeux, surtout avec la présentation ligne par ligne que tu proposes :

1
2
3
4
5
6
7
    0011010100
opé 0010010000
 =  0001000100

    0001000100
opé 0001000101
 =  0000000001

À toi de trouver à quel opérateur correspond opé. ;)

[Edit] Peut-être que je devrais te poser la question différemment : Quels sont les opérateurs binaires que tu connais ?

Édité par psycopy

+2 -0
Auteur du sujet

je connais le ou, le et, le xot, le not, les rotations etc.

Mais dans les trois premiers ca ne fonctionne pas… En operation simple ca ne fonctionne pas (remember les tables de verité, 0&1 = 0, 0&0 = 0, 1&1 = 1, 1 | (1/0) = 1, 0|0 = 0, et 1 xor 0 = 1, 1 xor 1 = 0, 0 xor 0 = 0)

Du coup je t'avoue donner ma lange a clem :(

Edit : okay. Bon, la je suis grave. Et dire que je fais un cours a des dut 1 demain…

Merci, et desole de la question x)

Édité par Ricocotam

+0 -0
Auteur du sujet

J'y ai pensé a un moment, puisque j'en fais plusieurs des operations logiques binaire. Mais le probleme c'est que mes nombres sont stocker sur des int (qui font plus que 10 bits) donc du coup ca peut vite etre la merde. Et quand on fait : 1 + 1 = 10 alors que moi je voudrais juste 0 :)

Mais sur d'autres operation, les additions et soustractions sont suffisants :)

+0 -0

Quand f({bits}) renvoie 1 uniquement si le nombre de 1 dans {bits} est impair, c'est un signe fort d'opération logique et non arithmétique. Bref, c'est une série de xor. Pas besoin de chercher midi à 14h.

Édité par lmghs

+0 -0
Auteur du sujet

Aah oui ! Je viens de le trouver le pourquoi du comment je faisais pas XOR !!

C'est parce qu'il est possible qu'il y ai 3 fois 1

Exemple :

1
2
3
4
5
6
7
8
9
0011010100

0010010000

0011000101

=

0000000001

C'est pour ça que je ne peux pas faire de XOR ! Désolé, mon exemple était mauvais :)

Édité par Ricocotam

+0 -0

En quoi l'opérateur binaire (i.e. d'arité 2) xor est différent de l'opérateur binaire +, ou - ? Il n'existe aucun opérateur mathématique/logique d'arité 3 de disponible dans la plupart des langages que nous utilisons.

Donc, explique nous pourquoi xor n'est pas bon, et que moins le serait ?

+0 -0
Auteur du sujet

Ni l'un ni l'autre sont bons.

En fait mon but c'est de mettre 0 dès qu'il y à plus de une fois un bit à 1.

Si on représente sous forme de tableau booleen (qu'on appel X), je veux que le résultat soit un tableau qui respecte cette contraintes : Chaque case i du tableau est égale à :

  • true si et seulement si une seule des case du du tableau X (n étant quelconque) est égale à true (autrement dit : qu'il n'y à qu'une seule fois true dans X)
  • false dans tout les autres cas.

Édité par Ricocotam

+1 -0

En fait mon but c'est de mettre 0 dès qu'il y à plus de une fois un bit à 1.

not(A) & not(B) & not(C) donc, non ?

J'ai rien dit, fait un tableau de carneau au pire, ça devrait le faire

Édité par Kje

+1 -0

OK. C'est plus clair là. Effectivement, xor ne fera pas l'affaire.

Soit a, b, c tes nombres. op le truc que l'on crée.
a op b doit correspondre à a xor b.

Pour a op b op c Il faut un premier xor pour neutraliser les 2 premiers 1 qui sont ensembles dans a et b.
Puis il faut chopper les 1 de c qui furent vrais dans le passé (en a ou b) -> (a+b)c. Et il va falloir les nettoyer (les mettre à 0) -> (a+b)c xor c, c'est la contribution positive de c. Et il faut aussi les nettoyer dans le précédant a xor b -> (a+b)c xor (a xor b). Et après, on peut tout fusionner avec un or.

NB: j'ai utilisé la notation de l'arithmétique de Boole (+ == or, . == and)

Pour plus d'arguments, il faut étendre la logique.

PS: et après, il faut simplifier les formules … ^^'

Édité par lmghs

+0 -0

J'ai au final un not(a+b).c + (a xor b).not(c) Si je ne me trompe pas.

NB: pfff. Après réflexion, avec une approche positive, plus simple, on a tout simplement pour 3 : c!a!b + b!a!c + a!b!c. Par contre cela me semble manquer de méthode et je soupçonne que cela va être plus dur à généraliser. A voir.

+0 -0
Auteur du sujet

En realite, je le fais avec 9 termes… J'ai pas tout compris pour t'avouer ^^ Je vais essayer de comprendre Sinon j'ai regarderles tables de karnaugh, je crois que ca peut le faire avec un outil :)

+0 -0

Pour 3 entrées on a : $S = a \bar b \bar c + \bar a b \bar c+ \bar a \bar b c$. Ce qui se simplifie bien en $S = (abc) \oplus a \oplus b \oplus c$. (merci Wolfram Alpha)

Mais en effet, la forme réduite ne se généralise pas bien. Il est possible que cela dépasse le cadre de la question du PO mais soyons tordu et imaginons que l’on veuille faire la même chose pour $n$ bits. Comme on peut s’en rendre compte en réfléchissant un peu au problème, il y a fondamentalement un état qui se propage dans le calcul. Exactement de la même façon qu’une retenu se propage dans une addition. On peut rendre cet état explicite en présentant l’algo comme ceci (Python) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def my_xor(bits):
    state = 1
    for bit in bits:
        if bit:
            state = 0 if state == 1 else 2
    return not bool(state)

PATTERN = "0000110000"
bits = map(lambda x: bool(int(x)), list(PATTERN))
print my_xor(bits)

Naturellement, si on veut avoir la même chose en combinatoire il faut dérouler la boucle. En écrivant ça dans un HDL, le synthétiseur peut le faire pour nous.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.numeric_std.ALL;


entity dummy is  
  generic ( n: natural := 5 );
  port(
    input : in std_logic_vector(n downto 0);
    output : out std_logic
  );
end entity;  

architecture beh of dummy is
begin
  
  process(input)
    variable state : std_logic_vector(1 downto 0);
  begin
    state := "01";
    for i in 0 to n loop
      if input(i) = '1' then
        if state = "01" then
          state := "00";
        else
          state := "10";
        end if;
      end if;
    end loop;
    
    if state /= "00" then
      output <= '0';
    else
      output <= '1';
    end if;
  end process;
    
end beh;

schéma RTL d’un "XOR" 6 entrées

Même sans entrer dans les détails du truc, on voit clairement que l’information se propage de droite à gauche du circuit. C’est notre fameux état qui à ici été déroulé entièrement.

Édité par simbilou

La répétition est la base de l’enseignement. — ☮ ♡

+1 -0

Et en version incrémentale, soit :

  • n entrées I1 à In (n == 3 dans ton exemple),
  • et les résultats si on applique l'opérateur que l'on écrit: Ri = Op(I1, … Ii).
  • Prenons le masque des résultats autorisés à l'étape i : Mi – il se souvient si un bit a été vu plus d'une fois à actif sur les i premières entrées.

On peut dire que Ri <- (Ri-1 ou Ii) et non Mi.
Soit, on prend le résultat précédent, on y ajoute les bits à 1 de la nouvelle entré Ii, et on vire tous les bits que l'on s'interdit.

Assez simplement, le calcul du masque se fait avec Mi <- Mi-1 ou ( Ri-1 et Ii ). Et pour y arriver, il faut poser R0 <- M0 <- 00000000

EDIT: la démo de bon fonctionnement de la version itérative: https://docs.google.com/spreadsheets/d/1xYrl87lJUDVEzy4chqHB2Rd9i4PJeyi-AAney2o-YTo/edit?usp=sharing

Édité par lmghs

+0 -0

Effectivement, ça n'était pas aussi simple que ce que j'ai cru au début. :D

Je sens venir une solution bien Pythonic à coup de reduce

1
2
3
from functools import reduce

funct = lambda *nums: reduce(int.__xor__, nums, reduce(int.__and__, nums))

1
2
3
4
5
6
7
>>> a = 0b101010
>>> b = 0b110011
>>> c = 0b010101
>>> d = 0b001000
>>> bin(funct(a, b, c, d))
'0b100'
>>> 

Édité par psycopy

+0 -0

De plus je dois coder en Java… =)

Ricocotam

Ça ne change rien, si tu comprend l’idée tu peux très bien le traduire en Java. Ta méthode de compter le nombre d’occurrence est bonne au passage. Pour faire le lien avec mon message précédent le nombre d’occurrence est une autre façon de calculer l’état. À la fin tu renvoi vrai si ce nombre vaut 1, faux sinon.

La répétition est la base de l’enseignement. — ☮ ♡

+0 -0

Alors avant que vous continuiez en python, je connais pas du tout.. De plus je dois coder en Java… =)

Ricocotam

Arf c'est bien dommage ! En même temps, je n'y connais rien au Java non-plus.

simbilou ayant fournit la réponse mathématique, mon message n'était que pour la frime, avec mon super-combo-reduce… (ouais, chuis fière de lui ! ^^ )

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte