La soustraction d'entiers non signés est-elle un comportement défini?

100

J'ai rencontré du code de quelqu'un qui semble croire qu'il y a un problème pour soustraire un entier non signé d'un autre entier du même type lorsque le résultat serait négatif. Ce code comme celui-ci serait donc incorrect même s'il fonctionnait sur la plupart des architectures.

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

C'est la seule citation vaguement pertinente de la norme C que j'ai pu trouver.

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 un supérieur à la plus grande valeur pouvant être représentée par le type résultant.

Je suppose que l'on pourrait prendre cette citation comme signifiant que lorsque l'opérande droit est plus grand, l'opération est ajustée pour être significative dans le contexte des nombres tronqués modulo.

c'est à dire

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

au lieu d'utiliser la sémantique signée dépendante de l'implémentation:

0x0000 - 0x0001 == (non signé) (0 + -1) == (0xFFFF mais aussi 0xFFFE ou 0x8001)

Quelle ou quelle interprétation est la bonne? Est-il défini du tout?

c standards unsigned integer-arithmetic LihO
la source
3
Le choix des mots dans la norme est malheureux. Qu'il «ne puisse jamais déborder» signifie qu'il ne s'agit pas d'une situation d'erreur. En utilisant la terminologie de la norme, au lieu de déborder la valeur «wraps».
danorton

Réponses:

107

Le résultat d'une soustraction générant un nombre négatif dans un type non signé est bien défini:

  1. [...] 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 un supérieur à la plus grande valeur pouvant être représentée par le type résultant. (ISO / CEI 9899: 1999 (F) §6.2.5 / 9)

Comme vous pouvez le voir, (unsigned)0 - (unsigned)1égal à -1 modulo UINT_MAX + 1, ou en d'autres termes, UINT_MAX.

Notez que bien qu'il dise "Un calcul impliquant des opérandes non signés ne peut jamais déborder", ce qui pourrait vous amener à croire qu'il ne s'applique que pour le dépassement de la limite supérieure, cela est présenté comme une motivation pour la partie de liaison réelle de la phrase: "a le 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 de un à la plus grande valeur pouvant être représentée par le type résultant. " Cette phrase n'est pas limitée au dépassement de la limite supérieure du type, et s'applique également aux valeurs trop faibles pour être représentées.

bdonlan
la source
2
Je vous remercie! Je vois maintenant l'interprétation qui me manquait. Je pense qu'ils auraient cependant pu choisir une formulation plus claire.
4
Je me sens tellement mieux maintenant, sachant que si une addition non signée roule à zéro et provoque le chaos, ce sera parce que uintc'était toujours destiné à représenter l' anneau mathématique des entiers à 0travers UINT_MAX, avec les opérations d'addition et de multiplication modulo UINT_MAX+1, et non parce que d'un débordement. Cependant, cela soulève la question de savoir pourquoi, si les anneaux sont un type de données si fondamental, le langage n'offre pas un support plus général pour les anneaux d'autres tailles.
Theodore Murdock
2
@TheodoreMurdock Je pense que la réponse à cette question est simple. Pour autant que je sache, le fait que ce soit une bague est une conséquence, pas une cause. La vraie exigence est que les types non signés doivent avoir tous leurs bits participant à la représentation de valeur. Un comportement semblable à un anneau en découle naturellement. Si vous voulez un tel comportement de la part d'autres types, effectuez votre calcul puis appliquez le module requis; qui utilise des opérateurs fondamentaux.
underscore_d
@underscore_d Bien sûr ... il est clair pourquoi ils ont pris la décision de conception. C'est juste amusant qu'ils aient écrit la spécification à peu près comme "il n'y a pas de dépassement / sous-dépassement arithmétique car le type de données est spécifié comme un anneau", comme si ce choix de conception signifiait que les programmeurs n'avaient pas à éviter soigneusement les sur- et sous -flow ou faire échouer leurs programmes de manière spectaculaire.
Theodore Murdock
121

Lorsque vous travaillez avec des types non signés , l'arithmétique modulaire (également appelée comportement «enveloppant» ) est en cours. Pour comprendre cette arithmétique modulaire , jetez simplement un œil à ces horloges:

entrez la description de l'image ici

9 + 4 = 1 ( 13 mod 12 ), donc dans l'autre sens c'est: 1 - 4 = 9 ( -3 mod 12 ). Le même principe est appliqué lorsque vous travaillez avec des types non signés. Si le type de résultat est unsigned, alors l'arithmétique modulaire a lieu.

Examinez maintenant les opérations suivantes en stockant le résultat sous forme de unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Lorsque vous voulez vous assurer que le résultat est signed, stockez-le dans une signedvariable ou transtypez-le en signed. Lorsque vous souhaitez obtenir la différence entre les nombres et vous assurer que l'arithmétique modulaire ne sera pas appliquée, vous devez envisager d'utiliser la abs()fonction définie dans stdlib.h:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Soyez très prudent, en particulier lors de l'écriture des conditions, car:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

mais

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...
LihO
la source
4
Belle avec les horloges, bien que la preuve en ferait la bonne réponse. La prémisse de la question comprend déjà l'affirmation que tout cela peut être vrai.
Courses de légèreté en orbite le
5
@LightnessRacesinOrbit: Merci. Je l'ai écrit parce que je pense que quelqu'un pourrait le trouver très utile. Je suis d'accord, que ce n'est pas une réponse complète.
LihO
4
La ligne int d = abs(five - seven);n'est pas bonne. Le premier five - sevenest calculé: la promotion laisse les types d'opérandes tels quels unsigned int, le résultat est calculé modulo (UINT_MAX+1)et s'évalue à UINT_MAX-1. Ensuite, cette valeur est le paramètre réel de abs, ce qui est une mauvaise nouvelle. abs(int)provoque un comportement non défini passer l'argument, car il est hors de portée, et abs(long long)peut probablement contenir la valeur, mais un comportement non défini se produit lorsque la valeur de retour est contrainte à intinitialiser d.
Ben Voigt
1
@LihO: Le seul opérateur en C ++ qui est sensible au contexte et qui agit différemment selon la façon dont son résultat est utilisé est un opérateur de conversion personnalisé operator T(). L'ajout dans les deux expressions dont nous discutons est effectué en type unsigned int, basé sur les types d'opérande. Le résultat de l'addition est unsigned int. Ensuite, ce résultat est implicitement converti en type requis dans le contexte, une conversion qui échoue car la valeur n'est pas représentable dans le nouveau type.
Ben Voigt
1
@LihO: Il peut être utile de penser à double x = 2/3;vsdouble y = 2.0/3;
Ben Voigt
5

Eh bien, la première interprétation est correcte. Cependant, votre raisonnement sur la «sémantique signée» dans ce contexte est faux.

Encore une fois, votre première interprétation est correcte. L'arithmétique non signée suit les règles de l'arithmétique modulo, ce qui signifie qu'elle est 0x0000 - 0x0001évaluée 0xFFFFpour les types non signés 32 bits.

Cependant, la seconde interprétation (celle basée sur la «sémantique signée») est également nécessaire pour produire le même résultat. C'est-à-dire que même si vous évaluez 0 - 1dans le domaine du type signé et que vous obtenez -1le résultat intermédiaire, il -1est toujours nécessaire de le produire 0xFFFFlorsqu'il sera converti ultérieurement en type non signé. Même si certaines plates-formes utilisent une représentation exotique pour les entiers signés (complément de 1, magnitude signée), cette plate-forme doit toujours appliquer des règles d'arithmétique modulo lors de la conversion de valeurs entières signées en valeurs non signées.

Par exemple, cette évaluation

signed int a = 0, b = 1;
unsigned int c = a - b;

est toujours garanti de produire UINT_MAXdans c, même si la plate-forme utilise une représentation exotique pour les entiers signés.

Fourmi
la source
4
Je pense que vous voulez dire des types non signés 16 bits, pas 32 bits.
xioxox
4

Avec des nombres non signés de type unsigned intou plus, en l'absence de conversions de type, a-best défini comme donnant le nombre non signé qui, lorsqu'il est ajouté b, donnera a. La conversion d'un nombre négatif en non signé est définie comme donnant le nombre qui, lorsqu'il est ajouté au nombre original inversé de signe, donnera zéro (donc convertir -5 en non signé donnera une valeur qui, lorsqu'elle est ajoutée à 5, donnera zéro) .

Notez que les nombres non signés plus petits que unsigned intpeuvent être promus en type intavant la soustraction, le comportement de a-bdépendra de la taille de int.

supercat
la source