Pourquoi le débordement d'entier non signé est-il défini, mais pas le débordement d'entier signé?

210

Le débordement d'entier non signé est bien défini par les normes C et C ++. Par exemple, la norme C99 ( §6.2.5/9) indique

Un calcul impliquant des opérandes non signés ne peut jamais déborder, car un résultat qui ne peut pas être représenté par le type entier non signé résultant est réduit modulo le nombre qui est supérieur à la plus grande valeur qui peut être représentée par le type résultant.

Cependant, les deux normes indiquent que le dépassement d'entier signé est un comportement non défini. Encore une fois, à partir de la norme C99 ( §3.4.3/1)

Un exemple de comportement indéfini est le comportement sur le débordement d'entier

Y a-t-il une raison historique ou (encore mieux!) Une raison technique à cet écart?

c++ c undefined-behavior integer-overflow Anthony Vallée-Dubois
la source
50
Probablement parce qu'il existe plus d'une façon de représenter des entiers signés. Le chemin n'est pas spécifié dans la norme, du moins pas en C ++.
juanchopanza
Lien utile: en.wikipedia.org/wiki/Signed_number_representations
Robᵩ
7
Ce que juanchopanza a dit est logique. Si je comprends bien, la norme C d'origine codifiait en grande partie la pratique existante. Si toutes les implémentations de l'époque convenaient de ce que le «débordement» non signé devrait faire, c'est une bonne raison de le normaliser. Ils n'étaient pas d'accord sur ce que le débordement signé devrait faire, de sorte que cela n'entre pas dans la norme.
2
@DavidElliman L'enveloppe non signée lors de l'addition est également facilement détectable ( if (a + b < a)). Le débordement lors de la multiplication est difficile pour les types signés et non signés.
5
@DavidElliman: Ce n'est pas seulement une question de savoir si vous pouvez le détecter, mais quel est le résultat. Dans une implémentation signe + valeur MAX_INT+1 == -0, alors que sur un complément à deux ce seraitINT_MIN
David Rodríguez - dribeas

Réponses:

163

La raison historique est que la plupart des implémentations C (compilateurs) ont simplement utilisé le comportement de débordement le plus facile à implémenter avec la représentation entière utilisée. Les implémentations C utilisaient généralement la même représentation que celle utilisée par le CPU - donc le comportement de débordement découle de la représentation entière utilisée par le CPU.

En pratique, seules les représentations de valeurs signées peuvent différer selon l'implémentation: complément à un, complément à deux, amplitude du signe. Pour un type non signé, il n'y a aucune raison pour que la norme autorise la variation car il n'y a qu'une seule représentation binaire évidente (la norme autorise uniquement la représentation binaire).

Citations pertinentes:

C99 6.2.6.1:3 :

Les valeurs stockées dans des champs binaires non signés et des objets de type char non signé doivent être représentées en utilisant une notation binaire pure.

C99 6.2.6.2:2 :

Si le bit de signe est un, la valeur doit être modifiée de l'une des manières suivantes:

- la valeur correspondante avec le bit de signe 0 est annulée ( signe et amplitude );

- le bit de signe a la valeur - (2 N ) ( complément à deux );

- le bit de signe a la valeur - (2 N - 1) ( son complément ).

De nos jours, tous les processeurs utilisent la représentation du complément à deux, mais le dépassement arithmétique signé reste indéfini et les fabricants de compilateurs souhaitent qu'il reste indéfini car ils utilisent cette indéfinie pour aider à l'optimisation. Voir par exemple ce blog de Ian Lance Taylor ou cette plainte d'Agner Fog, et les réponses à son rapport de bug.

Pascal Cuoq
la source
6
La note importante ici, cependant, est qu'il ne reste aucune architecture dans le monde moderne utilisant autre chose que l'arithmétique signée du complément à 2. Le fait que les normes de langage permettent toujours l'implémentation, par exemple sur un PDP-1, est un pur artefact historique.
Andy Ross
9
@AndyRoss mais il existe encore des systèmes (compilateurs OS +, certes avec une histoire ancienne) avec son complément et de nouvelles versions à partir de 2013. Un exemple: OS 2200.
ouah
3
@Andy Ross considéreriez-vous «aucune architecture ... utilisant autre chose que le complément de 2 ...» comprend aujourd'hui la gamme des DSP et des processeurs intégrés?
chux
11
@AndyRoss: Bien qu'il n'y ait «aucune» architecture utilisant autre chose que le complément 2s (pour une définition de «non»), il existe certainement des architectures DSP qui utilisent l'arithmétique saturante pour les entiers signés.
Stephen Canon
10
L'arithmétique signée saturante est définitivement conforme à la norme. Bien sûr, les instructions d'encapsulation doivent être utilisées pour l'arithmétique non signée, mais le compilateur a toujours les informations pour savoir si l'arithmétique non signée ou signée est en cours, il peut donc certainement choisir les instructions de manière appropriée.
caf
15

Mis à part la bonne réponse de Pascal (dont je suis sûr que c'est la principale motivation), il est également possible que certains processeurs provoquent une exception sur le débordement d'entier signé, ce qui bien sûr causerait des problèmes si le compilateur devait "arranger un autre comportement" ( par exemple, utilisez des instructions supplémentaires pour vérifier les débordements potentiels et calculer différemment dans ce cas).

Il convient également de noter que «comportement indéfini» ne signifie pas «ne fonctionne pas». Cela signifie que l'implémentation est autorisée à faire ce qu'elle veut dans cette situation. Cela implique de faire «la bonne chose» ainsi que «d'appeler la police» ou de «s'écraser». La plupart des compilateurs, lorsque cela est possible, choisissent "faire la bonne chose", en supposant que c'est relativement facile à définir (dans ce cas, c'est le cas). Cependant, si vous rencontrez des débordements dans les calculs, il est important de comprendre ce que cela entraîne réellement et que le compilateur PEUT faire autre chose que ce que vous attendez (et que cela peut très dépendre de la version du compilateur, des paramètres d'optimisation, etc.) .

Mats Petersson
la source
23
Les compilateurs ne veulent pas que vous comptiez sur eux pour faire la bonne chose, et la plupart d'entre eux vous le montreront dès que vous compilerez int f(int x) { return x+1>x; }avec optimisation. GCC et ICC optimisent les options ci-dessus avec return 1;.
Pascal Cuoq
1
Pour un exemple de programme qui donne des résultats différents en cas de intdébordement en fonction des niveaux d'optimisation, voir ideone.com/cki8nM Je pense que cela démontre que votre réponse donne de mauvais conseils.
Magnus Hoff
J'ai un peu modifié cette partie.
Mats Petersson
Si un C devait fournir un moyen de déclarer un entier "enveloppant le complément à deux signé", aucune plate-forme qui peut exécuter C ne devrait avoir beaucoup de mal à le supporter au moins modérément efficacement. La surcharge supplémentaire serait suffisante pour que le code n'utilise pas un tel type lorsque le comportement d'habillage n'est pas requis, mais la plupart des opérations sur les entiers complémentaires à deux sont identiques à celles sur des entiers non signés, à l'exception des comparaisons et des promotions.
supercat
1
Les valeurs négatives doivent exister et "fonctionner" pour que le compilateur fonctionne correctement. Il est bien sûr tout à fait possible de contourner le manque de valeurs signées dans un processeur et d'utiliser des valeurs non signées, soit comme complément à un, soit comme complément à deux, selon ce qui fait le plus sens basé sur le jeu d'instructions. Il serait généralement beaucoup plus lent de le faire que d'avoir une prise en charge matérielle, mais ce n'est pas différent des processeurs qui ne prennent pas en charge la virgule flottante dans le matériel, ou similaire - cela ajoute juste beaucoup de code supplémentaire.
Mats Petersson
10

Tout d'abord, veuillez noter que C11 3.4.3, comme tous les exemples et les notes de bas de page, n'est pas un texte normatif et n'est donc pas pertinent à citer!

Le texte pertinent qui déclare que le débordement d'entiers et de flottants est un comportement non défini est le suivant:

C11 6.5 / 5

Si une condition exceptionnelle se produit pendant l'évaluation d'une expression (c'est-à-dire si le résultat n'est pas défini mathématiquement ou n'est pas dans la plage de valeurs représentables pour son type), le comportement n'est pas défini.

Une clarification concernant spécifiquement le comportement des types entiers non signés peut être trouvée ici:

C11 6.2.5 / 9

La plage de valeurs non négatives d'un type entier signé est une sous-gamme du type entier non signé correspondant, et la représentation de la même valeur dans chaque type est la même. Un calcul impliquant des opérandes non signés ne peut jamais déborder, car un résultat qui ne peut pas être représenté par le type entier non signé résultant est réduit modulo le nombre qui est supérieur à la plus grande valeur qui peut être représentée par le type résultant.

Cela fait des types entiers non signés un cas spécial.

Notez également qu'il existe une exception si un type est converti en type signé et que l'ancienne valeur ne peut plus être représentée. Le comportement est alors simplement défini par l'implémentation, bien qu'un signal puisse être émis.

C11 6.3.1.3

6.3.1.3 Entiers signés et non signés

Lorsqu'une valeur de type entier est convertie en un autre type entier autre que _Bool, si la valeur peut être représentée par le nouveau type, elle reste inchangée.

Sinon, si le nouveau type n'est pas signé, la valeur est convertie en ajoutant ou en soustrayant à plusieurs reprises une valeur de plus que la valeur maximale pouvant être représentée dans le nouveau type jusqu'à ce que la valeur soit dans la plage du nouveau type.

Sinon, le nouveau type est signé et la valeur ne peut pas y être représentée; soit le résultat est défini par l'implémentation, soit un signal défini par l'implémentation est émis.

Lundin
la source
6

En plus des autres problèmes mentionnés, le fait d'avoir un habillage mathématique non signé fait que les types entiers non signés se comportent comme des groupes algébriques abstraits (ce qui signifie, entre autres, pour toute paire de valeurs Xet Y, il existera une autre valeur Ztelle que X+Z, si elle est correctement convertie , égal Yet Y-Zsera, s'il est correctement lancé, égalX). Si les valeurs non signées étaient simplement des types d'emplacement de stockage et non des types d'expression intermédiaire (par exemple, s'il n'y avait pas d'équivalent non signé du plus grand type entier, et que les opérations arithmétiques sur les types non signés se comportaient comme si elles avaient été converties pour la première fois en types signés plus grands, alors n'aurait pas autant besoin d'un comportement de wrapping défini, mais il est difficile de faire des calculs dans un type qui n'a pas par exemple d'inverse additif.

Cela aide dans les situations où le comportement de bouclage est réellement utile - par exemple avec des numéros de séquence TCP ou certains algorithmes, tels que le calcul de hachage. Cela peut également aider dans les situations où il est nécessaire de détecter un débordement, car effectuer des calculs et vérifier s'ils débordent est souvent plus facile que de vérifier à l'avance s'ils débordent, en particulier si les calculs impliquent le plus grand type entier disponible.

supercat
la source
Je ne suis pas tout à fait d'accord - pourquoi est-ce utile d'avoir un inverse additif? Je ne peux pas vraiment penser à une situation où le comportement de débordement est réellement utile ...
sleske
@sleske: Utiliser la décimale pour la lisibilité humaine, si un compteur d'énergie lit 0003 et que la lecture précédente était 9995, cela signifie-t-il que -9992 unités d'énergie ont été utilisées ou que 0008 unités d'énergie ont été utilisées? Le fait d'avoir 0003-9995 donne 0008 facilite le calcul de ce dernier résultat. Son rendement de -9992 le rendrait un peu plus gênant. Ne pas pouvoir le faire non plus, cependant, il faudrait comparer 0003 à 9995, remarquer que c'est moins, faire la soustraction inverse, soustraire le résultat de 9999 et ajouter 1.
supercat
@sleske: Il est également très utile pour les humains et les compilateurs de pouvoir appliquer les lois associatives, distributives et commutatives de l'arithmétique pour réécrire les expressions et les simplifier; par exemple, si l'expression a+b-cest calculée dans une boucle, mais bet csont constants dans cette boucle, il peut être utile de se déplacer calcul de l' (b-c)extérieur de la boucle, mais faire cela , il faudrait entre autres choses qui (b-c)donnent une valeur qui, lorsqu'elle est ajoutée à a, donnera a+b-c, ce qui nécessite à son tour d' cavoir un inverse additif.
supercat
: Merci pour les explications. Si je comprends bien, vos exemples supposent tous que vous voulez réellement gérer le débordement. Dans la plupart des cas que j'ai rencontrés, le débordement n'est pas souhaitable, et vous voulez l'empêcher, car le résultat d'un calcul avec débordement n'est pas utile. Par exemple, pour le compteur d'énergie, vous souhaiterez probablement utiliser un type tel qu'un débordement ne se produise jamais.
sleske
1
... de telle sorte que (a+b)-cégaux a+(b-c)si oui ou non la valeur arithmétique b-cest représentable dans le type, la substitution sera valable quelle que soit la plage de valeurs possibles pour (b-c).
supercat
1

Peut-être une autre raison pour laquelle l'arithmétique non signée est définie est parce que les nombres non signés forment des entiers modulo 2 ^ n, où n est la largeur du nombre non signé. Les nombres non signés sont simplement des nombres entiers représentés en utilisant des chiffres binaires au lieu de chiffres décimaux. La réalisation des opérations standard dans un système de module est bien connue.

La citation de l'OP fait référence à ce fait, mais met également en évidence le fait qu'il n'y a qu'une seule façon logique et non ambiguë de représenter des entiers non signés en binaire. En revanche, les nombres signés sont le plus souvent représentés en utilisant le complément à deux mais d'autres choix sont possibles comme décrit dans la norme (section 6.2.6.2).

La représentation du complément à deux permet à certaines opérations d'avoir plus de sens au format binaire. Par exemple, l'incrémentation des nombres négatifs est la même que pour les nombres positifs (attendez-vous dans des conditions de débordement). Certaines opérations au niveau de la machine peuvent être identiques pour les numéros signés et non signés. Cependant, lors de l'interprétation du résultat de ces opérations, certains cas n'ont pas de sens - débordement positif et négatif. De plus, les résultats de dépassement diffèrent selon la représentation sous-jacente signée.

yth
la source
Pour qu'une structure soit un champ, chaque élément de la structure autre que l'identité additive doit avoir un inverse multiplicatif. Une structure d'entiers congrus mod N sera un champ uniquement lorsque N est un ou premier [un champ dégénéré lorsque N == 1]. Y a-t-il quelque chose que vous pensez avoir manqué dans ma réponse?
supercat
Vous avez raison. Je suis devenu confus par les modules de puissance principale. Réponse originale modifiée.
2017
Très déroutant ici est qu'il est un champ d'ordre 2 ^ n, il est tout simplement pas d' anneau isomorphe aux entiers modulo 2 ^ n.
Kevin Ventullo
Et, 2 ^ 31-1 est un Mersenne Prime (mais 2 ^ 63-1 n'est pas un premier). Ainsi, mon idée originale a été ruinée. De plus, les tailles entières étaient différentes à l'époque. Donc, mon idée était au mieux révisionniste.
2018 à 2h53
Le fait que les entiers non signés forment un anneau (pas un champ), en prenant la partie de poids faible donne également un anneau, et effectuer des opérations sur la valeur entière puis tronquer se comportera comme effectuer les opérations uniquement sur la partie inférieure, étaient IMHO presque certainement des considérations.
supercat