Arithmétique binaire carry et overflow

par **LionO** » 12 Mai 2008, 17:08

Bonjour,

J'aimerai avoir une explication sur les notions de carry et overflow en arithmétique binaire : voici 2 exemples pour l'illustration :

Comment additionner 127 et 2 en complément à 2 et que faire du résultat qui est un overflow (sur 8 bit) ?

127 -> 01111111
2 -> +00000010

129 -> 10000001 -> résultat trop grand = overflow

Même question pour 127 et -2 qui donne un résultat sur 9 bit -> carry ?

127 -> 011111111
- 2 -> +111111110

125 -> 101111101 -> résultat ne tient pas sur 8 bit = carry

Merci

par **Jean_Luc** » 12 Mai 2008, 19:23

Salut,

Voici les définitions données par Intel:

Carry: 1 si une opération arithmétique génére une retenue "au dessus" du plus grand bit significatif du résultat, 0 dans les autres cas. Ce flag indique une condition de dépassement pour les opérations non-signées.

Overflow: 1 si le résultat est un nombre positif trop grand ou nombre négatif trop petit (en ne tenant pas compte du bit de signe), 0 dans les autres cas. Ce flag indique une condition de dépassement pour les opérations signées (complément à 2).

(Extrait de: IA-32 Intel Architecture Software Developer's Manual Vol 1)

par **LionO** » 12 Mai 2008, 19:53

Daccord, donc y a til une solution aux opérations ci dessus ?
Si le résultat de l'opération 127 + 2 ne peut pas être 129, quel est il ? Il doit y avoir une façon de traité ces cas la ?

par **Jean_Luc** » 12 Mai 2008, 20:08

Ben je ne comprends pas vraiment ta question...

127+2 = 129 => C'est OK en non-signé donc C=0
=> C'est pas OK en signé donc O=1

par **LionO** » 12 Mai 2008, 20:40

Ok je te remercie de tes réponses déja, en fait c'est peut etre super simple, mais j'ai pas encore pigé le truc, donc je récapitule :
- en non signé sur 8 bit je peux avoir des valeurs de 0 à 255 donc 129, c'est ok.
- en signé sur 8 bit je peux avoir des valeurs de 0 à 127 et de 0 à -128, donc 129 c'est pas ok donc que faut il faire avec le résultat 10000001 ? Inverser les bits ?
Même question pour 125, je me retrouve avec 9 bit à cause de la retenue, faut il omettre la retenue dans le cas ou il n'y plus rien à additionner ?
Merci

par **Jean_Luc** » 12 Mai 2008, 21:12

LionO a écrit:- en non signé sur 8 bit je peux avoir des valeurs de 0 à 255 donc 129, c'est ok.

Oui

LionO a écrit:- en signé sur 8 bit je peux avoir des valeurs de 0 à 127 et de 0 à -128, donc 129 c'est pas ok donc que faut il faire avec le résultat 10000001 ? Inverser les bits ?

Non, tu laisses le resultat tel quel. Il y aura 129 dans une variable non-signée et -127 dans une variable signée (mais avec un overflow).

LionO a écrit:Même question pour 125, je me retrouve avec 9 bit à cause de la retenue, faut il omettre la retenue dans le cas ou il n'y plus rien à additionner ?
Merci

Donc on aura 125 dans une variable non-signé avec une carry et également 125 dans une variable signée mais sans overflow.

par **abcd22** » 12 Mai 2008, 21:33

Bonjour,

LionO a écrit: 127 -> 011111111
- 2 -> +111111110

125 -> 101111101 -> résultat ne tient pas sur 8 bit = carry

Tu as mis un bit en trop dans les écritures de 127 et - 2. Il n'y a pas de problème dans ce cas, si tu sais lire en anglais regarde l'article wikipedia sur le complément à 2. Sinon la représentation des nombres dans les ordinateurs résulte de choix, il n'y a pas une unique solution pour un problème donné.

par **Jean_Luc** » 12 Mai 2008, 22:05

Il faut bien comprende que ces notions de carry et d'overflow sont liées au type d'opérations (signées ou pas) que l'on effectue. En gros le carry ça represente la retenue habituelle et l'overflow un dépassement lorsque l'on fait du signé en complement à 2.
Les définitions d'Intel sont bien claires.

par **LionO** » 13 Mai 2008, 14:12

Merci de vos réponses, seulement ce n'est pas encore super clair, voici un autre exemple :
je voudrais effectuer 3 - 1
donc je pose 0011 - 0001 = 0010 -> correct
maintenant si j'effectue la même chose en utilisant la méthode du complément à deux cela donne 0011 + 1111 = 10010 et je ne comprend pas ce résultat.

par **Jean_Luc** » 13 Mai 2008, 14:39

Code: Tout sélectionner: 0011 + 1111 [COLOR=Red]1[/COLOR]0010

Le résultat en signé c'est bien 2 (sur 4bits) et pas d'overflow.
Si le résultat est interprété comme le résultat d'une opération signée alors
c'est bon car pas d'overflow, en revanche si l'on interprète ce résultat comme le résultat d'une opération non signée (3+15=18) alors on a un dépassement (carry=1).

Je ne suis pas sur mais je pense que tu fais la confusion entre une opération
signée et non-signée. Bien entendu, l'opération est la même (une addition binaire) dans les 2 cas, la seule différence, c'est la manière dont on interprète le résultat. En gros, un processeur effectue toujours la même addition et positionne les 2 flags carry et overflow en vue d'une interprétation ultérieure
des résultat, notament lors d'un branchement sur une condition du type: si (a<-2) alors ...

par **LionO** » 13 Mai 2008, 16:02

Je commence à comprendre et à ne plus tout mélanger mais je dois quand même retrouver 2 comme résultat avec la méthode en complément à 2 non ? Or la je n'ai pas 2 en résultat a moins de supprimer le 1 dans 10010.

par **Jean_Luc** » 13 Mai 2008, 16:11

LionO a écrit:Je commence à comprendre et à ne plus tout mélanger mais je dois quand même retrouver 2 comme résultat avec la méthode en complément à 2 non ? Or la je n'ai pas 2 en résultat a moins de supprimer le 1 dans 10010.

Oui bien sur, et c'est bien ça il faut supprimer le 1 et garder uniquement les 4 bits de poids faible du résultat (4bits = la taille de ton registre ou de ta variable).
Pense bien que le fait d'avoir une carry lorsque l'on fait du complément à 2 n'est pas le signe d'un dépassement. L'exemple que tu cites l'illustre très bien.

par **LionO** » 13 Mai 2008, 16:29

Ok ma dernière question et je pense que ce sera bon aprés. Ma question concerne l'overflow cette fois avec cette exemple toujours sur 4 bits :
Je veux effectuer 4 + 4 = 8 ok mais trop grande valeur pour un entier signé en complément à 2, donc comment sait on que cette valeur est en fait -8.
0100 + 0100 = 1000 ?
Merci

par **Jean_Luc** » 13 Mai 2008, 16:38

Dans cet exemple, on a bien un overflow, car 8>7 et le registre contiendra -8.
(1000 = -8 en complément à 2 sur 4bits)
En non-signé pas de problème car pas de carry (4+4=8 => 1000 en non-signé).

par **Jean_Luc** » 13 Mai 2008, 16:47

Attention, l'article que je t'ai indiqué sur wikipedia contient des informations
invalides. Je pense que tu les verras.
Je vais les corriger...

par **LionO** » 13 Mai 2008, 17:02

Ok préviens moi une fois que tu as corrigé car je n'ai pas vu les erreurs.
J'essaye encore de comprendre le système d'overflow et surtout le résultat, voici un autre exemple avec 7 + 6 = 13.
0111 + 0110 = 1101, il y overflow biensur en entier signé, sa je l'ai compris. Par contre en complément à 2, 1101 équivaut à -3 en décimal.
Maintenant y a til un moyen de passer de 1101 à -3 en décimal par le calcul ?
J'ai fait le complément à 2 du nombre 1101 ce qui donne 0010 + 1 = 0011 ce qui est la valeur absolue de -3. Mais comment sait on que c'est un chiffre négatif en regardant uniquement le résultat de 0111 + 0110 = 1101 ?

par **Jean_Luc** » 13 Mai 2008, 17:20

LionO a écrit: Mais comment sait on que c'est un chiffre négatif en regardant uniquement le résultat de 0111 + 0110 = 1101 ?

C'est le bit de signe qui donne l'info.
1101. 1 => -, 0 => +.
Donc dans cet exemple on sait que l'on a un nombre négatif, on calcule son complement à 2 comme tu l'as fait et ça donne - (-3) = 3.

PS: J'ai corrigé WikiPedia...

Arithmétique binaire carry et overflow

Arithmétique binaire carry et overflow

Qui est en ligne