Operation binaire

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

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 ?

Pareil, j'ai du mal à ne pas penser au justicier de l'espace…

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)

Tu vas trop loin. Pas besoin de regarder dans les opérations logiques, les additions et soustractions de nombres en base 2 suffiront. Par contre, je dois avoir certaines limites, parce que mon résultat final serait -1, pas 1.

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

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.

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

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 ?

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.

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

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 … ^^'

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.

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

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;

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.

J'ai rien compris

Je crois que je vais me rabattre sur une methode plus simple en comptant le nombre d'occurence non?

Et en version incrémentale, soit :

• n entrées I₁ à I_n (n == 3 dans ton exemple),
• et les résultats si on applique l'opérateur que l'on écrit: R_i = Op(I₁, … I_i).
• Prenons le masque des résultats autorisés à l'étape i : M_i – 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 R_i <- (R_i-1 ou I_i) et non M_i.
Soit, on prend le résultat précédent, on y ajoute les bits à 1 de la nouvelle entré I_i, et on vire tous les bits que l'on s'interdit.

Assez simplement, le calcul du masque se fait avec M_i <- M_i-1 ou ( R_i-1 et I_i ). Et pour y arriver, il faut poser R₀ <- M₀ <- 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

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

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'
>>> 

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

Ç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.

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 ! )