Addition binaire

Version imprimable

29/05/2016, 15h05
bj303931

1 pièce(s) jointe(s)

Addition binaire
Bonjour, j'essaye de faire une additon en c en passant par le binaire. ;)

Le schéma de l'additionneur est: Pièce jointe 211149

L'équation logique est donc: (a XOR b) OU (a ET b) avec a et b les nombres à additionner.

Or, ce code renvoye 3 au lieu de 5. :calim2:
Code:

1 2 3 4 5 6 7 8 9 #include <stdio.h> unsigned int add (unsigned int a, unsigned int b){ return a^b|a&b;} void main(){ int r = add(2,3); printf("%d", r); }
29/05/2016, 16h21
Pyramidev

Bonjour.

Citation:

Envoyé par bj303931

L'équation logique est donc: (a XOR b) OU (a ET b) avec a et b les nombres à additionner.

Non.

Soient a et b deux entiers naturels. Soit s = a + b.
Soient (a₀, a₁, a₂, ...) les bits de a, a₀ étant le bit de poids faible.
Soient (b₀, b₁, b₂, ...) les bits de b, b₀ étant le bit de poids faible.
Soient (s₀, s₁, s₂, ...) les bits de s, s₀ étant le bit de poids faible.
On veut connaître les bits de s.

On a :
s₀ = a₀ XOR b₀
s₁ = a₁ XOR b₁ XOR c₀ avec c₀ = a₀ ET b₀ la retenue pour l'itération 0.
s₂ = a₂ XOR b₂ XOR c₁ avec c₁ = (a₁ ET b₁) OU (a₁ ET c₀) OU (b₁ ET c₀) la retenue pour l'itération 1.

De manière générale, pour tout entier k supérieur ou égal à 1 :
s_k = a_k XOR b_k XOR c_k-1 avec c_k-1 la retenue de l'itération k-1.
c_k = (a_k ET b_k) OU (a_k ET c_k-1) OU (b_k ET c_k-1)

Plus de détails sur Wikipédia :
https://fr.wikipedia.org/wiki/Additionneur
29/05/2016, 16h28
Bktero

Pourquoi prendre soin d'utiliser des unsigned int dans ta fonction d'addition si c'est pour utiliser un int signé dans la fonction main ?....

Au hasard, je pencherai pourune question de priorité des opérateurs. Ton calcul est donné avec des parenthèses, mais elles disparaissent dans ta traduction en C.
29/05/2016, 17h14
Pyramidev

Citation:

Envoyé par Bktero

Au hasard, je pencherai pour une question de priorité des opérateurs.

Le ET bit à bit est prioritaire sur le XOR bit à bit qui est prioritaire sur le OU bit à bit, donc a^b|a&b équivaut bien à (a^b)|(a&b).
http://en.cppreference.com/w/cpp/lan...tor_precedence

Le problème de fond, c'est que (a^b)|(a&b) n'a rien à voir avec a+b.
En fait, (a^b)|(a&b) équivaut à a|b.

Bonjour,
on peut considérer ça comme des opérations sur des vecteurs de bits ...

Code:

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
39
40
41
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
 
void bitvector_add(uint32_t a, uint32_t b, uint32_t *add, uint32_t *carry);
uint32_t uint32_add(uint32_t a, uint32_t b);
 
void bitvector_add(uint32_t a, uint32_t b, uint32_t *add, uint32_t *carry)
{
  *add=a^b;
  *carry=a&b;
}
 
uint32_t uint32_add(uint32_t a, uint32_t b)
{
  uint32_t add;
  uint32_t carry;
 
  do {
    bitvector_add(a,b,&add,&carry);
    a=add;
    b=carry<<1;
  } while (b!=0);
 
  return a;
}
 
int main(void)
{
  uint32_t a,b;
 
  printf("a=");
  scanf("%"SCNu32, &a);
 
  printf("b=");
  scanf("%"SCNu32, &b);
 
  printf("a+b=%"PRIu32"\n", uint32_add(a,b));
 
  return 0;
}

29/05/2016, 21h26
Bktero

Citation:

Envoyé par Pyramidev

Le ET bit à bit est prioritaire sur le XOR bit à bit qui est prioritaire sur le OU bit à bit, donc a^b|a&b équivaut bien à (a^b)|(a&b).
http://en.cppreference.com/w/cpp/lan...tor_precedence

Le problème de fond, c'est que (a^b)|(a&b) n'a rien à voir avec a+b.
En fait, (a^b)|(a&b) équivaut à a|b.

Arf... J'étais parti du postulat que la formule était bonne.... Un problème de priorité etait donc la seule possible erreur.

Après avoir posté je me suis dit que c'était bizarre car il me semblait que le OU avait une priorité faible. Ce que tu confirmes ;)

Ca ne marche toujours pas...

Merci, pour toutes vos idées. ;) J'ai essayé de les mettre bout à bout mais ça ne marche toujours pas... :(

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
void addi (int a, int b, int *add, int *r){
        *add=a^b^*r;
        *r=a&b|a&*r|b&*r;
                }
 
int addition (int a, int b){
        int add;
        int r;
        while(b!=0){addi(a, b, &r, &add);
                a=add;
                b=r<<1;}
        return a;}
 
void main(){
int r = addition(2,3);
printf("%d", r);
}

Celui-ci renvoie 2 au lieu de 5. :yaisse3:

31/05/2016, 09h48
Matt_Houston

Lecture de variable non initialisée, le résultat est indéfini.

Ca ne marche toujours pas...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
void addi (int a, int b, int *add, int *r){
        *add=a^b^*r;
        *r=a&b|a&*r|b&*r;
                }
 
int addition (int a, int b){
        int add=0;
        int r=0;
        while(b!=0){addi(a, b, &r, &add);
                a=add;
                b=r<<1;}
        return a;}
 
void main(){
int r = addition(2,3);
printf("%d", r);
}

Aucun changements. :ptdr:

31/05/2016, 19h36
Pyramidev

C'est normal que ça ne marche pas.
Tu ne peux pas fusionner au hasard mes formules avec celles qui sont dans l'algorithme utilisé par picodev.

L'algorithme utilisé par picodev se base sur l'égalité suivante :
a + b == (a^b) + ((a&b)<<1)

Dans la boucle de l'algorithme utilisé par picodev, à chaque itération, on remplace a par a^b et b par (a&b)<<1.
Ainsi, la valeur de a + b est inchangée.
La boucle s'arrête quand b == 0, c'est-à-dire quand a contient la somme des entiers naturels a et b de départ.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
#include<conio.h>
void main()
{
  clrcsr();
  int a,b:
  a=2,b=3;
  c=a^b||a&b;
  printf("the value of c ="&c);
  scanf("%d%d",&c&c);
  getch();
}