Discussion :

[CompuTux]

Bonjour,

J'ai un problème pour coder des entiers relatifs.

Par exemple coder -8 sur 4 bits :

8=1000

Après où met-on le bit de signe ??? (puisque l'on est sur 4 bits)

Autre exemple coder -125 sur un octet :

125=01111101
donc -125=11111101

C'est juste ?

Mais si on fait la somme : 01111101+11111101=101111010 là on est sur 9 bits; je ne comprends pas comment rester sur un octet...
De plus on devrait trouver 00000000 puisque 125-125=0.

Merci pour vos réponse !

[Mac LAK]

Ton problème est lié à quatre choses :

• Le bit de signe est toujours en plus du nombre de bits significatifs. Donc, 8 demandant 4 bits pour être codé, tenir compte du signe exige d'avoir 5 bits...
• Les opérations s'effectuent en augmentant le nombre de bits, donc en propageant le bit de signe, pour s'adapter au plus long des deux opérandes.
• Un nombre négatif, en binaire, se calcule en faisant le complément à deux du nombre positif équivalent (négation binaire + 1).
  Donc, "-8" s'écrit NOT(01000)+1 = (10111)+1 = 11000 (5 bits), ou 11111000 (8 bits).
  Ton -125 sur 8 bits s'écrit NOT(01111101)+1 = (10000010)+1 = 10000011, et non pas 11111101.
• En cas de dépassement (a.k.a carry ou retenue), les bits supplémentaires sont purement et simplement éliminés.

Quelques liens de cours d'arithmétique binaire :
Cours 1
Cours 2
Cours 3

Bonne lecture !

[CompuTux]

Ok si je comprends bien, -8 n'est pas codable sur 4 bits.

De plus -125 codé en signe + valeur absolue, ajouté à 125 même codage donne un résultat faux.

C'est ce que voulais montrer le prof je pense.

D'où l'intérêt de coder les entiers relatifs en complément à 2 !

Merci bien Mac Lak !

[Mac LAK]

Ok si je comprends bien, -8 n'est pas codable sur 4 bits.

Tu as bien compris.

De plus -125 codé en signe + valeur absolue, ajouté à 125 même codage donne un résultat faux.

En effet : la somme est alors égale à (125*2)+bit de signe, donc une sorte de "-250", ce qui n'est pas le résultat recherché.

D'où l'intérêt de coder les entiers relatifs en complément à 2 !

En réalité, additionner deux nombres opposés en binaire ne produit pas réellement zéro : si tu codes sur N bits, le résultat de (k+(-k)) est égal à 2^N, chiffre qui nécessite (N+1) bits pour être écrit en binaire, et qui vaut "un" suivi de N fois "zéro".
Or, en repassant sur N bits, on a donc bien zéro partout, plus un bit de dépassement (retenue/carry) qui permet de propager la retenue, notamment lorsque l'on manipule des nombres binaires plus grands que le mot-machine (ex : opérations sur des données 64 bits sur un processeur 32 bits, qui nécessite deux opérations 32 bits + propagation de la retenue).

C'est donc pour ça que l'opposé d'un nombre en binaire est le complément à deux : tu peux facilement le vérifier par toi-même, c'est un bon exercice d'ailleurs. Et cela t'explique aussi pourquoi il est impératif de connaître le nombre total de bits utilisés pour l'encodage si l'on veut écrire un nombre binaire "négatif"... (-1) codé sur 8, 16 ou 32 bits, ce sont trois nombres différents !!

Tant que tu retiens bien que les opérations binaires se font sur un nombre figé de bits, avec éventuellement propagation d'une retenue, le binaire est plutôt simple. Si par contre tu prends le réflexe (hélas courant) d'omettre les zéros non-significatifs, qui permettent d'avoir la taille en bits des nombres, alors tu vas aller assez vite dans le mur... En général, dès le premier NOT binaire, d'ailleurs.

Quand on te demande d'écrire / utiliser un nombre en binaire, ta première question doit toujours être "Sur combien de bits ?". Graves-toi ça dans la tête, et le binaire ne te posera (presque) jamais de problèmes.

[ijk-ref]

Ok si je comprends bien, -8 n'est pas codable sur 4 bits.

Tu as bien compris.

Pardon ! Pour moi si :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1000 : -8
1001 : -7
1010 : -6
1011 : -5
1100 : -4
1101 : -3
1110 : -2
1111 : -1
0000 : +0
0001 : +1
0010 : +2
0011 : +3
0100 : +4
0101 : +5
0110 : +6
0111 : +7

Tout comme un entier signé sur 8 bits a sa portée de -128 à 127
un entier signé sur 4 bits a sa portée de -8 à 7

[Mac LAK]

C'est vrai dans un contexte d'implémentation, notamment pour ne pas perdre une des valeurs utile.

Mais côté arithmétique, ton 1000 est ambigü : il peut valoir -8, 8, ou... "moins zéro" !!! Et les trois interprétations seraient plus ou moins cohérentes, en plus...

Par convention, et en arithmétique binaire (donc, des maths "pures"), il vaut mieux éviter d'utiliser la valeur limite négative. En implémentation (en informatique, donc), on expose ce cas particulier.
Mais dire que c'est -8 ou 8, c'est une simple convention.

[ijk-ref]

C'est vrai dans un contexte d'implémentation, notamment pour ne pas perdre une des valeurs utile.

Mais côté arithmétique, ton 1000 est ambigü : il peut valoir -8, 8, ou... "moins zéro" !!! Et les trois interprétations seraient plus ou moins cohérentes, en plus...

Par convention, et en arithmétique binaire (donc, des maths "pures"), il vaut mieux éviter d'utiliser la valeur limite négative. En implémentation (en informatique, donc), on expose ce cas particulier.
Mais dire que c'est -8 ou 8, c'est une simple convention.

Pas super ton rattrapage aux branches !

En tout cas il ne peut en aucun valoir "moins zéro" !!!

TOUTES les conventions classiques utilisent le dernier bit pour le signe. C'est à dire que lorsqu'il est à 1 le nombre est négatif. Point barre... ce nombre n'est pas plus particulier que les autres.

[Mac LAK]

En tout cas il ne peut en aucun valoir "moins zéro" !!!

Et pourtant... En représentation naïve (bit de signe + valeur absolue), qui est un autre codage des entiers relatifs tout à fait légitime même s'il ne permet pas les opérations classiques, tu as bien une ambigüité.
Tout est question de conventions.

TOUTES les conventions classiques utilisent le dernier bit pour le signe. C'est à dire que lorsqu'il est à 1 le nombre est négatif.

Ce sont des conventions d'implémentation, c'est à dire ce qui existe réellement sur des CPU.
Côté arithmétique binaire pure et dure, donc des maths, ce cas est litigieux. Il est par contre plus simple de prendre en compte d'abord et avant tout le bit de signe dans une implémentation, notamment pour mettre à jour les bons flags du CPU après une opération.

Que tu prennes comme valeur limite 8 ou -8 pour 1000, ça ne change pas le fait que 7+1 = 0111 + 0001 = 1000 : il vaut quoi, alors, 8 ou -8 ??? Parce que dans le même temps : (-7) + (-1) = 1001 + 1111 = 1000 : si ça, c'est pas ambigu...

En fait, ça ne l'est pas, mais pour le voir, il faudrait conserver le 5ème bit. Or, comme ce codage des relatifs impose un nombre de bits fixé, tu perds l'information te permettant de discriminer le cas. D'un point de vue mathématique, tu as une congruence sur 16 (2^4) : normalement, elle va de 0 à 15. Après, tu peux "recadrer" ce domaine comme ça te chante via n'importe quelle bijection, mais aucune n'est "mieux" ou "plus valide" qu'une autre.

Tu confonds les maths et l'application des maths, ou si tu préfères l'algo et le code implémentant l'algo en question.

[ijk-ref]

Et pourtant... En représentation naïve (bit de signe + valeur absolue), qui est un autre codage des entiers relatifs tout à fait légitime même s'il ne permet pas les opérations classiques, tu as bien une ambigüité.
Tout est question de conventions

... sauf que depuis le début on représente tous les autres nombres en complément à deux... donc je ne vois pas "au nom de quoi" tu voudrais un traitement particulier au nombre "1000" !?

C'est à dire que s'il peut parfaitement représenter -8 ou 8 (plus exactement 8 modulo 16) il ne peut en aucun cas représenter "-0" avec cette convention.

Tu confonds les maths et l'application des maths, ou si tu préfères l'algo et le code implémentant l'algo en question.

Je ne confonds rien du tout. Ce n'est pas moi qui est confirmé que l'on ne pouvait pas représenter le nombre -8 avec 4 bits

... alors que c'était surement le piège dans son exercice !

[Mac LAK]

... sauf que depuis le début

J'ai bien mis "en représentation naïve", relis...

Je ne confonds rien du tout.

Avec 4 bits, tu peux représenter très exactement 16 valeurs distinctes, ni plus, ni moins. Le fait d'avoir -8 ou 8 pour la valeur limite n'est qu'une question de convention.
Mathématiquement parlant, les deux sont parfaitement légitimes et valides, et produisent tous les deux une valeur correcte (cf. post précédent) : il n'y a donc pas de raison particulière, sauf habitude d'implémentation, de privilégier l'une plutôt que l'autre, ou même de décider que ce n'est pas une valeur légale, d'ailleurs !

Par rapport à la question initiale, qui sous-entend de pouvoir coder à la fois 8 et -8, tu dois passer sur 5 bits pour permettre ça (et conserver un intervalle sy. Sinon, tu perds la possibilité de coder soit l'un, soit l'autre en fonction de la convention choisie.

Ce que je précise en disant que le bit de signe est "en plus" des bits significatifs (16 bits signés = 15 bits utiles = valeurs absolues de 0 à ... 32767 !). Le fait qu'il "reste" une valeur possible dans l'intervalle (nombre constitué du bit de signe à 1 suivi de zéros) et qu'on ne la rendre pas invalide est un effet de bord.

Pour l'anecdote, j'utilise très couramment (en interface avec l'électronique notamment) une convention qui veut que, sur un nombre 16 bits, le zéro soit "1000000000000000"... C'est à dire la valeur médiane de l'intervalle (le "-32767" valant 1, le "+32767" valant 1 répété 16 fois, un zéro binaire est une erreur de conversion / overflow). Même si les opérations binaires classiques ne peuvent pas être appliquées telles quelles, cela reste une représentation acceptable des entiers binaires relatifs... Et c'est directement issu d'un CPU, pourtant !!