Dissortingbution efficace sans signature à signer évitant le comportement défini par l’implémentation

Je veux définir une fonction qui prend un argument unsigned int comme et retourne un int congruent modulo UINT_MAX + 1 à l’argument.

Une première tentative pourrait ressembler à ceci:

 int unsigned_to_signed(unsigned n) { return static_cast(n); } 

Mais, comme tout juriste le sait, le passage de non signé à signé pour des valeurs supérieures à INT_MAX est défini par la mise en œuvre.

Je veux implémenter cela de telle sorte que (a) il ne repose que sur le comportement prescrit par la spécification; et (b) il comstack en une no-op sur n’importe quelle machine moderne et optimise le compilateur.

Comme pour les machines bizarres … S’il n’y a pas de modulo intégré UINT_MAX + 1 signé dans le unsigned int, disons que je veux lancer une exception. S’il y en a plus d’un (je ne suis pas sûr que ce soit possible), disons que je veux le plus grand.

OK, deuxième tentative:

 int unsigned_to_signed(unsigned n) { int int_n = static_cast(n); if (n == static_cast(int_n)) return int_n; // else do something long and complicated } 

Je ne m’inquiète pas beaucoup de l’efficacité lorsque je ne suis pas sur un système typique à deux compléments, car, à mon humble avis, c’est peu probable. Et si mon code devient un goulot d’étranglement sur les systèmes omniprésents de magnitude des signes de 2050, eh bien, je parie que quelqu’un peut le comprendre et l’optimiser à ce moment-là.

Maintenant, cette deuxième tentative est assez proche de ce que je veux. Bien que la conversion en int soit définie par l’implémentation pour certaines entrées, le retour à unsigned est garanti par la norme pour préserver la valeur modulo UINT_MAX + 1. Donc, le conditionnel vérifie exactement ce que je veux, et il ne comstackra rien sur aucun système que je suis susceptible de rencontrer.

Cependant … je continue à lancer dans int sans vérifier au préalable si elle invoquera un comportement défini par l’implémentation. Sur un système hypothétique en 2050, il pourrait faire qui-sait-quoi. Alors disons que je veux éviter cela.

Question: A quoi devrait ressembler ma “troisième tentative”?

Pour récapituler, je veux:

  • Cast de unsigned int à signé int
  • Conservez la valeur mod UINT_MAX + 1
  • Invoquer uniquement un comportement normalisé
  • Comstackz dans un no-op sur une machine typique à deux compléments avec un compilateur optimisé

[Mettre à jour]

Permettez-moi de donner un exemple pour montrer pourquoi ce n’est pas une question anodine.

Considérons une implémentation C ++ hypothétique avec les propriétés suivantes:

  • sizeof(int) est égal à 4
  • sizeof(unsigned) est égal à 4
  • INT_MAX est égal à 32767
  • INT_MIN est égal à -2 32 + 32768
  • UINT_MAX est égal à 2 32 – 1
  • L’arithmétique sur int est modulo 2 32 (dans la plage INT_MIN à INT_MAX )
  • std::numeric_limits::is_modulo est vrai
  • Le cast unsigned n à int préserve la valeur pour 0 <= n <= 32767 et renvoie zéro sinon

Sur cette implémentation hypothétique, il y a exactement une valeur int congru (mod UINT_MAX + 1) à chaque valeur unsigned . Donc, ma question serait bien définie.

Je prétends que cette implémentation C ++ hypothétique est entièrement conforme aux spécifications C ++ 98, C ++ 03 et C ++ 11. J’avoue que je n’ai pas mémorisé chaque mot de tous … Mais je crois avoir lu attentivement les sections pertinentes. Donc, si vous voulez que j’accepte votre réponse, vous devez (a) citer une spécification qui exclut cette implémentation hypothétique ou (b) la traiter correctement.

En effet, une réponse correcte doit gérer chaque implémentation hypothétique permise par la norme. C’est ce que signifie “invoquer uniquement un comportement normalisé”, par définition.

Incidemment, notez que std::numeric_limits::is_modulo est totalement inutile pour plusieurs raisons. D’une part, cela peut être true même si les dissortingbutions non signées à signées ne fonctionnent pas pour les grandes valeurs non signées. Pour un autre, cela peut être true même sur les systèmes à un seul complément ou à grand nombre de signes, si l’arithmétique est simplement modulo la plage entière entière. Etc. Si votre réponse dépend de is_modulo , c’est faux.

[Mise à jour 2]

La réponse de hvd m’a appris quelque chose: mon implémentation C ++ hypothétique pour les entiers n’est pas permise par le moderne C. Les normes C99 et C11 sont très spécifiques sur la représentation des entiers signés; en effet, ils ne permettent que deux compléments, un complément et une ampleur de signe (section 6.2.6.2 alinéa (2)).

Mais le C ++ n’est pas le C. En l’occurrence, ce fait est au coeur même de ma question.

Le standard C ++ 98 original était basé sur le C89 beaucoup plus ancien, qui dit (section 3.1.2.5):

Pour chacun des types d’entiers signés, il existe un type d’entier non signé correspondant (mais différent) (désigné par le mot-clé non signé) qui utilise la même quantité de stockage (y compris les informations de signe) et présente les mêmes exigences d’alignement. La plage de valeurs non négatives d’un type d’entier signé est une sous-plage du type d’entier non signé correspondant, et la représentation de la même valeur dans chaque type est identique.

C89 ne dit rien sur le fait d’avoir un seul bit de signe ou de n’autoriser que deux-complément / un-complément / signe-magnitude.

La norme C ++ 98 a adopté ce langage presque textuellement (paragraphe 3.9.1 alinéa (3)):

Pour chacun des types d’entiers signés, il existe un type d’entier non signé correspondant (mais différent): ” unsigned char “, ” unsigned short int “, ” unsigned int ” et ” unsigned long int “, chacun occupant la même quantité de stockage et a les mêmes exigences d’alignement (3.9) que le type d’entier signé correspondant; c’est-à-dire que chaque type d’ entier signé a la même représentation d’object que le type d’ entier non signé correspondant. La plage des valeurs non négatives d’un type entier signé est une sous-plage du type entier non signé correspondant, et la représentation des valeurs de chaque type signé / non signé correspondant doit être la même.

Le standard C ++ 03 utilise un langage essentiellement identique, tout comme C ++ 11.

Aucune spécification C ++ standard ne limite ses représentations entières signées à aucune spécification C, pour autant que je sache. Et rien n’impose un seul signe ou quelque chose du genre. Tout ce qu’il dit, c’est que les entiers signés non négatifs doivent être une sous-gamme des non signés correspondants.

Donc, encore une fois, je prétends que INT_MAX = 32767 avec INT_MIN = -2 32 +32768 est autorisé. Si votre réponse suppose le contraire, il est incorrect à moins que vous ne citiez une norme C ++ qui me prouve le contraire.