Distribution efficace non signée à signée évitant les comportements définis par l'implémentation

Question

Je veux définir une fonction qui prend un unsigned int comme argument et renvoie un int congrus modulo UINT_MAX+1 pour l'argument.

Une première tentative pourrait ressembler à ceci:

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

Mais comme toute langue, l'avocat sait, la conversion de non signé signé pour des valeurs plus grandes que INT_MAX la mise en œuvre est définie.

Je veux mettre en œuvre la présente tel que (a) il ne repose que sur le comportement mandaté par la spécification; et (b) il compile dans un no-op sur toute machine moderne et d'optimisation du compilateur.

Comme pour les étranges machines... Si il n'y a pas signé d'int congrus modulo UINT_MAX+1 pour les unsigned int, disons que je veux lancer une exception. Si il n'y a plus d'un (je ne suis pas sûr que c'est possible), disons que je veux la plus grande.

OK, la deuxième tentative:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

Je n'ai pas beaucoup de soins au sujet de l'efficacité quand je ne suis pas sur un deux-système du complément, car à mon humble avis, c'est peu probable. Et si mon code devient un goulet d'étranglement sur l'omniprésence d'un signe-amplitude systèmes de 2050, eh bien, je parie que quelqu'un peut comprendre et d'optimiser l'époque.

Maintenant, cette deuxième tentative est assez proche de ce que je veux. Bien que le cast int est mise en œuvre définies pour certains intrants, la fonte de retour à l' unsigned est garanti par la norme afin de préserver la valeur modulo UINT_MAX+1. Si la condition n'vérifier exactement ce que je veux, et compiler en rien sur tout le système je suis susceptible de rencontrer.

Cependant... je suis encore un casting pour int sans vérifier d'abord si elle va invoquer la mise en œuvre définies par le comportement. Sur un hypothétique système en 2050, elle pourrait faire de qui-sait-quoi. Donc, disons que je veux éviter.

Question: Quelle devrait être ma "troisième tentative"?

Pour résumer, je veux:

• Moulés à partir de unsigned int signé int
• Préserver la valeur mod UINT_MAX+1
• Invoquer standard mandat comportement
• Compiler dans un no-op sur un deux-en complément de la machine avec l'optimisation du compilateur

[Mise à jour]

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

Prenons le C++ mise en œuvre 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³² + 32768
• UINT_MAX est égal à 2³² - 1
• L'arithmétique sur int modulo 2³² (dans la gamme INT_MIN par INT_MAX)
• std::numeric_limits<int>::is_modulo est vrai
• Casting unsigned n d'int conserve la valeur pour 0 <= n <= 32767 et les rendements zéro sinon

Sur cette hypothétique mise en œuvre, il y a exactement un int de la valeur congruents (mod UINT_MAX+1) pour chaque unsigned de la valeur. Donc ma question serait bien définis.

Je prétends que cet hypothétique C++ mise en œuvre pleinement conforme à la C++98, C++03, et de C++11 cahier des charges. J'avoue que je n'ai pas mémorisé chaque parole de tous... Mais je crois que j'ai lu les sections pertinentes soigneusement. Donc, si vous voulez que j'accepte votre réponse, vous devez (a) citer un spec que les règles de cette hypothétique mise en œuvre ou (b) les manipuler correctement.

En effet, une réponse correcte doit gérer chaque hypothétique mise en œuvre permise par la norme. C'est ce qui "invoquer standard mandat comportement" signifie, par définition.

D'ailleurs, notez qu' std::numeric_limits<int>::is_modulo est tout à fait inutile ici pour de multiples raisons. Pour une chose, il peut être true même si non signé-à-signé jette de ne pas travailler pour de grandes valeurs non signées. Pour l'autre, il peut être true même sur un complément ou un signe-amplitude systèmes, si l'arithmétique est simplement modulo l'ensemble de l'intervalle entier. Et ainsi de suite. Si votre réponse dépend is_modulo, c'est faux.

[Mise à jour 2]

hvd réponse m'a appris quelque chose: Mon hypothétique implémentation C++ pour les entiers est pas permise par les techniques modernes de C. C99 et C11 normes sont très spécifiques au sujet de la représentation des entiers signés; en effet, ils ne permettent que deux en complément, ceux-compléter et signer magnitude (section 6.2.6.2 paragraphe (2); ).

Mais le C++ n'est pas C. Comme il s'avère, de ce fait se trouve au cœur de ma question.

Le C++98 norme a été basé sur la plus ancienne C89, qui dit (section 3.1.2.5):

Pour chaque entier signé types, il existe un correspondant (mais différents) type entier non signé (désigné par le mot-clé non signé), qui utilise la même quantité de stockage (y compris le signe de l'information) et a les mêmes exigences alignement. La gamme de non négatif valeurs d'un entier signé de type est un sous-groupe de la correspondant de type entier non signé, et la représentation de la même valeur dans chaque type est le même.

C89 ne dit rien sur un seul bit de signe ou permettant seulement deux-complément/-complément d'ouverture de l'ampleur.

Le C++98 standard adopté cette langue presque mot à mot (section 3.9.1 paragraphe (3)):

Pour chaque entier signé types, il existe un correspondant (mais différentes) type entier non signé: "unsigned char", "unsigned short int", "unsigned int"et "unsigned long int", chacun de qui occupe la même quantité de stockage et a le même alignement exigences (3.9) que le type entier signé ; que est, chaque entier signé de type a, l'objet même de la représentation comme son correspondant entier non signé de type. La gamme de positif les valeurs d'un entier signé de type est un sous-groupe de correspondants type entier non signé, et la valeur de la représentation de chaque correspondant signed/unsigned type doit être le même.

Le C++03 standard utilise essentiellement identique de la langue, comme le fait de C++11.

Pas de C++ standard spec limite son entier signé auprès de tout C spec, autant que je puis dire. Et il n'y a rien de mandater un seul bit de signe ou quelque chose du genre. Tout ce qu'elle dit, c'est que non-négatif entiers signés doivent être un sous-groupe de correspondants non signé.

Donc, encore une fois je demande que INT_MAX=32767 avec INT_MIN=-2³²+32768 est autorisée. Si votre réponse suppose sinon, elle est incorrecte, à moins que vous citez un C++ standard prouver que j'ai tort.

Answer 1

L'expansion sur user71404 de réponse:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

Si x >= INT_MIN (garder les règles de la promotion de l'esprit, INT_MIN est converti en unsigned), alors x - INT_MIN <= INT_MAX, donc ce n'aurez pas de débordement.

Si ce n'est pas évident, jetez un oeil à la demande "Si x >= -4u, alors x + 4 <= 3.", et gardez à l'esprit que INT_MAX sera au moins égal à la valeur mathématique de INT_MIN - 1.

Sur les systèmes les plus courants, où !(x <= INT_MAX) implique x >= INT_MIN, l'optimiseur doit être en mesure (et sur mon système, en est capable) pour supprimer la deuxième case, de déterminer que les deux return déclarations peuvent être compilés dans le même code, et de supprimer la première case. L'assembly généré liste:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

L'hypothétique mise en œuvre dans votre question:

• INT_MAX est égal à 32767
• INT_MIN est égal à -2³² + 32768

n'est pas possible, n'a donc pas besoin d'une attention particulière. INT_MIN sera égale à -INT_MAX, ou d' -INT_MAX - 1. Cela découle de C représentation des types d'entiers (6.2.6.2), qui exige n des bits à la valeur de bits, un bit à bit de signe, et n'autorise qu'un seul piège de la représentation (non compris les représentations qui sont invalides en raison de rembourrage bits), à savoir celui qui serait autrement représentent négatif zéro / -INT_MAX - 1. C++ ne permet pas à un nombre entier quelconque des représentations au-delà de ce que le C permet.

Mise à jour: Microsoft compilateur apparemment n'est pas d'avis qu' x > 10 et x >= 11 tester la même chose. Il ne génère le code souhaité s' x >= INT_MIN est remplacé par x > INT_MIN - 1u, il peut détecter que la négation de l' x <= INT_MAX (sur cette plate-forme).

[Mise à jour à partir interlocuteur (Nemo), de l'élaboration de notre discussion ci-dessous]

Je crois que cette réponse fonctionne dans tous les cas, mais compliqué raisons. J'ai la chance d'attribution de la prime à cette solution, mais j'ai envie de capturer tous les détails croustillants dans le cas où quelqu'un se soucie.

Nous allons commencer avec le C++11, section 18.3.3:

Tableau 31 décrit l'en-tête <climits>.

...

Le contenu est le même que la bibliothèque Standard C de l'en-tête <limits.h>.

Ici, un Standard "C" signifie que le C99, dont les spécifications limite sérieusement la représentation des entiers signés. Ils sont comme des entiers non signés, mais avec un peu dédié à "signer" et de zéro ou plusieurs bits dédiés à "padding". Le rembourrage bits ne contribuent pas à la valeur de l'entier, et le bit de signe contribue seulement que deux en complément, complément, ou le signe-amplitude.

Depuis C++11 hérite de l' <climits> macros de C99, INT_MIN est soit -INT_MAX ou -INT_MAX-1, et hvd code est garanti pour fonctionner. (Notez que, en raison du rembourrage, INT_MAX pourrait être beaucoup moins que UINT_MAX/2... Mais grâce à la manière signé->unsigned jette travail, cette réponse poignées fine).

C++03/C++98 est plus délicat. Il utilise la même formulation pour hériter <climits> de "Standard C", mais maintenant Standard "C" signifie C89/C90.

L'ensemble de ces -- C++98, C++03, C89/C90 -- le libellé je donne à ma question, mais également inclure ce (C++03 section 3.9.1 paragraphe 7):

Les représentations de l'ensemble des types de définir des valeurs par l'utilisation d'un pure binaire système de numération.(44) [Exemple: International Norme permet complément de 2, 1 de complément et signé de l'ampleur représentations pour les types intégraux.]

Note de bas de page (44) définit la "pure numération binaire du système":

Une position de représentation pour les entiers qui utilise les chiffres binaires 0 et 1, dans lequel les valeurs représentées par une succession de bits sont additif, commencer par 1, et sont multipliés par les intégrales puissance de 2, sauf peut-être pour le bit à la position la plus haute.

Ce qui est intéressant à propos de cette formulation est qu'il est en contradiction avec lui-même, parce que la définition de "pure numération binaire système" n'a pas permis un signe et l'ampleur de la représentation! Il ne permet pas de haut bits d'avoir, disons, la valeur -2^n-1 (complément à deux) ou -(2^n-1-1) (complément). Mais il n'y a pas de valeur pour le peu élevé que les résultats dans le signe et l'ampleur.

De toute façon, mon "hypothétique mise en œuvre" n'est pas considéré comme "pur binaire" en vertu de cette définition, il est exclu.

Cependant, le fait que la haute bit est spécial signifie que nous pouvons l'imaginer contribuant aucune valeur: Une petite valeur positive, énorme valeur positive, de petite valeur négative, ou à une énorme valeur négative. (Si le bit de signe peut contribuer -(2^n-1-1), pourquoi pas -(2^n-1-2)? etc.)

Donc, imaginons un entier signé de représentation qui affecte une wacky valeur de "signe".

Une petite valeur positive pour le bit de signe entraînerait une plage positive int (éventuellement aussi grand que unsigned), et hvd du code gère cela très bien.

Une énorme valeur positive pour le bit de signe entraînerait int ayant un maximum de plus de unsigned, ce qui est interdit.

Une énorme valeur négative pour le bit de signe entraînerait int représentant un non-contiguë à une gamme de valeurs, et d'autres libellé dans la spécification des règles.

Enfin, que diriez-vous d'un bit de signe qui contribue à une petite quantité négative? Pourrions-nous avoir un 1 dans le "bit de signe" contribuer, disons, de -37 à la valeur de l'int? Alors INT_MAX serait (dire) 2³¹-1 et INT_MIN serait -37?

Cela aurait pour conséquence, dans certains nombres d'avoir deux représentations... Mais ceux-compléter donne deux représentations à zéro, et qui est autorisé conformément à la "Exemple". Nulle part dans la spec dire que le zéro est le seul entier qui peut avoir deux représentations. Je pense donc que cette nouvelle hypothétique est autorisé par les spécifications.

En effet, une valeur négative de -1 en bas à -INT_MAX-1 semble être admissible en tant que valeur pour le "bit de signe", mais rien de plus petite taille (de peur que la fourchette de non-contigus). En d'autres termes, INT_MIN pourrait être quelque chose d' -INT_MAX-1 à -1.

Maintenant, devinez quoi? Pour la deuxième distribution dans hvd du code pour éviter de mise en œuvre définies par le comportement, nous avons juste besoin d' x - (unsigned)INT_MIN inférieur ou égal à INT_MAX. Nous avons seulement montré INT_MIN d'au moins -INT_MAX-1. De toute évidence, x est au plus UINT_MAX. Le moulage d'un nombre négatif non signé est le même que l'ajout d' UINT_MAX+1. Mettre tout cela ensemble:

x - (unsigned)INT_MIN <= INT_MAX

si et seulement si

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

Cette dernière est ce que nous a juste montré, de sorte que même dans cette perverse cas, le code fonctionne réellement.

Qui épuise toutes les possibilités, mettant ainsi un terme à cette extrêmement exercice académique.

Bottom line: Il y a quelques gravement sous-comportement spécifié pour les entiers signés en C89/C90 qui a hérité du C++98/C++03. Il est fixé en C99, et de C++11 indirectement hérite de la résoudre en intégrant <limits.h> de C99. Mais même en C++11 conserve l'auto-contradictoire "pure représentation binaire" les mots...

Answer 2

Ce code repose uniquement sur le comportement, imposé par la spécification, de sorte que l'exigence (a) est facilement satisfaite:

 int unsigned_to_signed(unsigned n)
{
  int result = INT_MAX;

  if (n > INT_MAX && n < INT_MIN)
    throw runtime_error("no signed int for this number");

  for (unsigned i = INT_MAX; i != n; --i)
    --result;

  return result;
}
 

Ce n'est pas si facile avec l'exigence (b). Ceci compile en un no-op avec gcc 4.6.3 (-Os, -O2, -O3) et avec le croc 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 refuse d'optimiser cela. Et je n'ai aucune information sur Visual C.

Answer 3

Vous pouvez explicitement dire au compilateur ce que vous voulez faire:

 int unsigned_to_signed(unsigned n) {
  if (n > INT_MAX) {
    if (n <= UINT_MAX + INT_MIN) {
      throw "no result";
    }
    return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1);
  } else {
    return static_cast<int>(n);
  }
}
 

Compile avec gcc 4.7.2 pour x86_64-linux ( g++ -O -S test.cpp ) à

 _Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret
 

Answer 4

std::numeric_limits<int>::is_modulo est une compilation constante de temps. de sorte que vous pouvez l'utiliser pour le modèle de la spécialisation. problème résolu, au moins si compilateur joue avec inline.

#include <limits>
#include <stdexcept>
#include <string>

#ifdef TESTING_SF
    bool const testing_sf = true;
#else
    bool const testing_sf = false;
#endif

// C++ "extensions"
namespace cppx {
    using std::runtime_error;
    using std::string;

    inline bool hopefully( bool const c ) { return c; }
    inline bool throw_x( string const& s ) { throw runtime_error( s ); }

}  // namespace cppx

// C++ "portability perversions"
namespace cppp {
    using cppx::hopefully;
    using cppx::throw_x;
    using std::numeric_limits;

    namespace detail {
        template< bool isTwosComplement >
        int signed_from( unsigned const n )
        {
            if( n <= unsigned( numeric_limits<int>::max() ) )
            {
                return static_cast<int>( n );
            }

            unsigned const u_max = unsigned( -1 );
            unsigned const u_half = u_max/2 + 1;

            if( n == u_half )
            {
                throw_x( "signed_from: unsupported value (negative max)" );
            }

            int const i_quarter = static_cast<int>( u_half/2 );
            int const int_n1 = static_cast<int>( n - u_half );
            int const int_n2 = int_n1 - i_quarter;
            int const int_n3 = int_n2 - i_quarter;

            hopefully( n == static_cast<unsigned>( int_n3 ) )
                || throw_x( "signed_from: range error" );

            return int_n3;
        }

        template<>
        inline int signed_from<true>( unsigned const n )
        {
            return static_cast<int>( n );
        }
    }    // namespace detail

    inline int signed_from( unsigned const n )
    {
        bool const is_modulo = numeric_limits< int >::is_modulo;
        return detail::signed_from< is_modulo && !testing_sf >( n );
    }
}    // namespace cppp

#include <iostream>
using namespace std;
int main()
{
    int const x = cppp::signed_from( -42u );
    wcout << x << endl;
}

---

MODIFIER

: Correction du code pour éviter les pièges potentiels sur la non-modulaire-int machines (une seule est connue, à savoir la archaically configuré versions de la Unisys Clearpath). Pour plus de simplicité il suffit de ne pas soutenir la valeur -2^n-1 où n est le nombre d' int de la valeur des bits, sur la machine (c'est à dire, sur la Clearpath). dans la pratique, cette valeur ne sera pas pris en charge par la machine (c'est à dire, avec le signe et l'ampleur ou l'1 complément représentation).

Answer 5

Je pense que le type int est au moins deux octets, donc les INT_MIN et INT_MAX peuvent changer dans différentes plates-formes.

Types fondamentaux

≤climits≥ entête