Efficace non signé-à-signé fonte d'éviter la mise en œuvre définies par le comportement

Expansion sur user71404 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), puis x - INT_MIN <= INT_MAX, si ce n'aurez pas de débordement.

Si ce n'est pas évident, jetez un oeil à la demande "Si x >= -4u, puis 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 de trop. L'assembly généré inscription:

__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 à -INT_MAX - 1. Cela découle de C représentation des types d'entiers (6.2.6.2), ce qui nécessite n 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 ne semble pas remarquer que x > 10 et x >= 11 tester la même chose. Il ne génère le code désiré si x >= INT_MIN est remplacé par x > INT_MIN - 1u, qu'il peut détecter comme la négation de 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:

Table 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, ceux-complément, ou le signe-amplitude.

Depuis C++11 hérite de la <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.

Tous 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) (ceux 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 le "signe" peu.

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 avoir 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 de sortir.

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 entraînerait un 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 c'est le zéro seulement 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 peut-être quelque chose de -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 x - (unsigned)INT_MIN inférieure ou égale à INT_MAX. Nous avons seulement montré INT_MIN est au moins -INT_MAX-1. Évidemment, x est au plus UINT_MAX. Le moulage d'un nombre négatif non signé est le même que l'ajout de 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

Ce dernier 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.

Bas de ligne: 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...

Vous pouvez indiquer explicitement 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

Mon argent est sur l'utilisation de memcpy. Tout bon compilateur sait optimiser loin:

#include <stdio.h>
#include <memory.h>
#include <limits.h>

static inline int unsigned_to_signed(unsigned n)
{
    int result;
    memcpy( &result, &n, sizeof(result));
    return result;
}

int main(int argc, const char * argv[])
{
    unsigned int x = UINT_MAX - 1;
    int xx = unsigned_to_signed(x);
    return xx;
}

Pour moi (Xcode 8.3.2, Apple LLVM 8.1, -O3), qui produit:

_main:                                  ## @main
Lfunc_begin0:
    .loc    1 21 0                  ## /Users/Someone/main.c:21:0
    .cfi_startproc
## BB#0:
    pushq    %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    ##DEBUG_VALUE: main:argc <- %EDI
    ##DEBUG_VALUE: main:argv <- %RSI
Ltmp3:
    ##DEBUG_VALUE: main:x <- 2147483646
    ##DEBUG_VALUE: main:xx <- 2147483646
    .loc    1 24 5 prologue_end     ## /Users/Someone/main.c:24:5
    movl    $-2, %eax
    popq    %rbp
    retq
Ltmp4:
Lfunc_end0:
    .cfi_endproc

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

Types fondamentaux

≤climits≥ - tête