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

Question

Je suis tombé sur le code de quelqu'un qui semble croire qu'il y a un problème à soustraire un entier non signé d'un autre entier du même type lorsque le résultat serait négatif. Ainsi, un code comme celui-ci serait incorrect même s'il se trouve fonctionner 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épasser, car un résultat qui ne peut pas être représenté par le type d'entier non signé résultant est résultant est réduit modulo le nombre qui est supérieur d'une unité à la plus grande valeur valeur qui peut être représentée par le type résultant.

Je suppose que l'on pourrait interpréter cette citation comme signifiant que lorsque l'opérande de droite 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

par opposition à l'utilisation de la sémantique de signature dépendant 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-elle définie du tout ?

Answer 1

Lorsque vous travaillez avec non signé types, arithmétique modulaire (également connu sous le nom de "envelopper" comportement) a lieu. Pour comprendre ce arithmétique modulaire Jetez un coup d'œil à ces horloges :

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

---

Maintenant, regardez les opérations suivantes qui stockent le résultat en tant que 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 puis l'a stocké dans signed ou la transformer en signed . Lorsque vous souhaitez obtenir la différence entre des nombres et vous assurer que l'arithmétique modulaire ne sera pas appliquée, vous devez envisager d'utiliser abs() définie dans stdlib.h :

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

Soyez très prudent, surtout lorsque vous écrivez les 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)
    // ...

Answer 2

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 d'entier non signé résultant est réduit modulo le nombre qui est supérieur d'une unité à la plus grande valeur qui peut être représentée par le type résultant. (ISO/IEC 9899:1999 (E) §6.2.5/9)

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

Notez que, bien qu'il soit indiqué "Un calcul impliquant des opérandes non signés ne peut jamais déborder", ce qui pourrait vous amener à penser que cela ne s'applique qu'en cas de dépassement de la limite supérieure, cela est présenté comme une motivation pour la partie contraignante de la phrase : "un résultat qui ne peut pas être représenté par le type d'entier non signé résultant est réduit modulo le nombre qui est supérieur d'une unité à la plus grande valeur qui peut ê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.

Answer 3

La première interprétation est correcte. Cependant, votre raisonnement sur la "sémantique signée" dans ce contexte est erroné.

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 que 0x0000 - 0x0001 évalue à 0xFFFF pour les types non signés 32 bits.

Cependant, la deuxième interprétation (celle basée sur la "sémantique signée") est également requise pour produire le même résultat. C'est-à-dire que même si vous évaluez 0 - 1 dans le domaine du type signé et obtenir -1 comme résultat intermédiaire, cette -1 est toujours nécessaire pour produire 0xFFFF alors que plus tard il sera converti en type non signé. Même si une plate-forme utilise une représentation exotique pour les entiers signés (complément à 1, magnitude signée), cette plate-forme est toujours tenue d'appliquer les règles de l'arithmétique modulo lors de la conversion des 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 garantie de produire UINT_MAX en c même si la plate-forme utilise une représentation exotique pour les nombres entiers signés.

Answer 4

Avec les nombres non signés de type unsigned int ou plus, en l'absence de conversions de type, a-b est 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é en signe, donne zéro (ainsi, la conversion de -5 en non signé donnera une valeur qui, ajoutée à 5, donnera zéro).

Notez que les nombres non signés inférieurs à unsigned int peut être promu au type int avant la soustraction, le comportement de a-b dépendra de la taille de int .

Answer 5

Je voulais juste ajouter un commentaire à @LihO, mais le manque de réputation m'oblige à ajouter une réponse.

J'ai fait ce qui suit en utilisant python

-2 % int('0xffffffff',base=16)
Out[5]: 4294967293L

Je pense que vous devriez le changer en

unsigned int a = five - seven;      // a = (-2 % (0xFFFFFFFFul + 1)) = 4294967294