Reparto eficiente sin firmar para evitar el comportamiento definido por la implementación

Quiero definir una función que tome un unsigned intargumento como y devuelva un intmódulo congruente UINT_MAX + 1 al argumento.

Un primer intento podría verse así:

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

Pero como sabe cualquier abogado de idiomas, la conversión de valores sin firmar a firmados para valores mayores que INT_MAX está definida por la implementación.

Quiero implementar esto de tal manera que (a) solo se base en el comportamiento exigido por la especificación; y (b) compila en un no-op en cualquier máquina moderna y optimiza el compilador.

En cuanto a las máquinas extrañas ... Si no hay un int congruente con el módulo UINT_MAX + 1 con el int sin firmar, digamos que quiero lanzar una excepción. Si hay más de uno (no estoy seguro de que sea posible), digamos que quiero el más grande.

OK, segundo intento:

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
}

No me importa mucho la eficiencia cuando no estoy en un sistema típico de complemento a dos, ya que en mi humilde opinión eso es poco probable. Y si mi código se convierte en un cuello de botella en los omnipresentes sistemas de magnitud de signo de 2050, bueno, apuesto a que alguien puede resolverlo y optimizarlo entonces.

Ahora, este segundo intento está bastante cerca de lo que quiero. Aunque la conversión a intestá definida por la implementación para algunas entradas, la unsignedconversión a está garantizada por el estándar para preservar el valor módulo UINT_MAX + 1. Entonces, el condicional verifica exactamente lo que quiero, y no se compilará en ningún sistema que pueda encontrar.

Sin embargo ... todavía estoy lanzando intsin verificar primero si invocará el comportamiento definido por la implementación. En algún sistema hipotético en 2050 podría hacer quién sabe qué. Digamos que quiero evitar eso.

Pregunta: ¿Cómo debería ser mi "tercer intento"?

En resumen, quiero:

• Transmitir de int sin firmar a int firmado
• Conservar el valor mod UINT_MAX + 1
• Invocar solo el comportamiento obligatorio estándar
• Compile en una operación no operativa en una máquina típica de complemento a dos con compilador de optimización

[Actualizar]

Permítanme dar un ejemplo para mostrar por qué esta no es una pregunta trivial.

Considere una implementación hipotética de C ++ con las siguientes propiedades:

• sizeof(int) es igual a 4
• sizeof(unsigned) es igual a 4
• INT_MAX es igual a 32767
• INT_MINes igual a -2 ³² + 32768
• UINT_MAXes igual a 2 ³² - 1
• La aritmética intactivada es módulo 2 ³² (en el rango INT_MINhasta INT_MAX)
• std::numeric_limits<int>::is_modulo es verdad
• La conversión unsigned nto int conserva el valor de 0 <= n <= 32767 y, en caso contrario, arroja cero

En esta implementación hipotética, hay exactamente un intvalor congruente (mod UINT_MAX + 1) para cada unsignedvalor. Entonces mi pregunta estaría bien definida.

Afirmo que esta implementación hipotética de C ++ cumple totalmente con las especificaciones de C ++ 98, C ++ 03 y C ++ 11. Admito que no he memorizado cada palabra de todas ... Pero creo que he leído las secciones relevantes con atención. Entonces, si desea que acepte su respuesta, debe (a) citar una especificación que descarte esta implementación hipotética o (b) manejarla correctamente.

De hecho, una respuesta correcta debe manejar cada implementación hipotética permitida por el estándar. Eso es lo que significa, por definición, "invocar sólo el comportamiento obligatorio estándar".

Por cierto, tenga en cuenta que std::numeric_limits<int>::is_moduloaquí es completamente inútil por múltiples razones. Por un lado, puede ser trueincluso si las conversiones sin firmar no funcionan para valores sin firmar grandes. Por otro lado, puede ser trueincluso en sistemas de complemento a uno o de magnitud de signo, si la aritmética es simplemente módulo todo el rango entero. Y así. Si su respuesta depende de is_modulo, está mal.

[Actualización 2]

La respuesta de hvd me enseñó algo: Mi implementación hipotética de C ++ para enteros no está permitida por el C. moderno. Los estándares C99 y C11 son muy específicos sobre la representación de enteros con signo; de hecho, solo permiten complemento a dos, complemento a uno y magnitud de signo (sección 6.2.6.2 párrafo (2);).

Pero C ++ no es C. Como resultado, este hecho está en el corazón de mi pregunta.

El estándar C ++ 98 original se basó en el C89 mucho más antiguo, que dice (sección 3.1.2.5):

Para cada uno de los tipos de enteros con signo, existe un tipo de entero sin signo correspondiente (pero diferente) (designado con la palabra clave unsigned) que usa la misma cantidad de almacenamiento (incluida la información de signo) y tiene los mismos requisitos de alineación. El rango de valores no negativos de un tipo de entero con signo es un subrango del tipo de entero sin signo correspondiente, y la representación del mismo valor en cada tipo es la misma.

C89 no dice nada sobre tener solo un bit de signo o solo permitir dos-complemento / uno-complemento / signo-magnitud.

El estándar C ++ 98 adoptó este lenguaje casi literalmente (sección 3.9.1 párrafo (3)):

Para cada uno de los tipos de enteros con signo, existe un tipo de entero sin signo correspondiente (pero diferente) : " unsigned char", " unsigned short int", " unsigned int" y " unsigned long int", cada uno de los cuales ocupa la misma cantidad de almacenamiento y tiene los mismos requisitos de alineación (3.9 ) como el tipo entero con signo correspondiente; es decir, cada tipo de entero con signo tiene la misma representación de objeto que su correspondiente tipo de entero sin signo . El rango de valores no negativos de un tipo de entero con signo es un subrango del tipo de entero sin signo correspondiente, y la representación del valor de cada tipo con / sin signo correspondiente será la misma.

El estándar C ++ 03 utiliza un lenguaje esencialmente idéntico, al igual que C ++ 11.

Ninguna especificación estándar de C ++ restringe sus representaciones enteras con signo a ninguna especificación de C, por lo que puedo decir. Y no hay nada que exija un bit de signo único ni nada por el estilo. Todo lo que dice es que los enteros con signo no negativo deben ser un subrango del correspondiente sin signo.

Entonces, nuevamente afirmo que INT_MAX = 32767 con INT_MIN = -2 ³² +32768 está permitido. Si su respuesta asume lo contrario, es incorrecta a menos que cite un estándar C ++ que demuestre que estoy equivocado.

Ampliando la respuesta de user71404:

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(tenga en cuenta las reglas de la promoción, INT_MINse convierte en unsigned), entonces x - INT_MIN <= INT_MAX, esto no tendrá ningún desbordamiento.

Si eso no es obvio, eche un vistazo a la afirmación "Si x >= -4u, entonces x + 4 <= 3.", Y tenga en cuenta que INT_MAXserá igual al menos al valor matemático de -INT_MIN - 1.

En los sistemas más comunes, donde !(x <= INT_MAX)implica x >= INT_MIN, el optimizador debería poder (y en mi sistema, puede) eliminar la segunda verificación, determinar que las dos returndeclaraciones se pueden compilar en el mismo código y eliminar la primera verificación también. Listado de ensamblaje generado:

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

La implementación hipotética en su pregunta:

• INT_MAX es igual a 32767
• INT_MIN es igual a -2 ³² + 32768

no es posible, por lo que no necesita una consideración especial. INT_MINserá igual a cualquiera -INT_MAX, o a -INT_MAX - 1. Esto se desprende de la representación de C de tipos enteros (6.2.6.2), que requiere que los nbits sean bits de valor, un bit sea un bit de signo y solo permite una representación de trampa única (sin incluir representaciones que no son válidas debido a los bits de relleno), es decir, el que de otro modo representaría cero / negativo -INT_MAX - 1. C ++ no permite ninguna representación de números enteros más allá de lo que C permite.

Actualización : el compilador de Microsoft aparentemente no se da cuenta de esox > 10yx >= 11prueba lo mismo. Solo genera el código deseado six >= INT_MINse reemplaza conx > INT_MIN - 1u, que puede detectar como la negación dex <= INT_MAX(en esta plataforma).

[Actualización del interlocutor (Nemo), que detalla nuestra discusión a continuación]

Ahora creo que esta respuesta funciona en todos los casos, pero por razones complicadas. Es probable que otorgue la recompensa por esta solución, pero quiero capturar todos los detalles sangrientos en caso de que a alguien le importe.

Comencemos con C ++ 11, sección 18.3.3:

La Tabla 31 describe el encabezado <climits>.

...

El contenido es el mismo que el del encabezado de la biblioteca C estándar <limits.h>.

Aquí, "Estándar C" significa C99, cuya especificación restringe severamente la representación de enteros con signo. Son como enteros sin signo, pero con un bit dedicado al "signo" y cero o más bits dedicados al "relleno". Los bits de relleno no contribuyen al valor del entero, y el bit de signo contribuye solo como complemento a dos, complemento a uno o magnitud de signo.

Dado que C ++ 11 hereda las <climits>macros de C99, INT_MIN es -INT_MAX o -INT_MAX-1, y se garantiza que el código de hvd funciona. (Tenga en cuenta que, debido al relleno, INT_MAX podría ser mucho menor que UINT_MAX / 2 ... Pero gracias a la forma en que funcionan los moldes firmados-> sin firmar, esta respuesta lo maneja bien).

C ++ 03 / C ++ 98 es más complicado. Utiliza la misma redacción para heredar <climits>de "Estándar C", pero ahora "Estándar C" significa C89 / C90.

Todos estos, C ++ 98, C ++ 03, C89 / C90, tienen la redacción que doy en mi pregunta, pero también incluyen esto (C ++ 03 sección 3.9.1 párrafo 7):

Las representaciones de tipos integrales definirán valores mediante el uso de un sistema de numeración binario puro. (44) [ Ejemplo : esta Norma Internacional permite representaciones en complemento a 2, complemento a 1 y magnitud con signo para tipos integrales].

La nota al pie (44) define "sistema de numeración binario puro":

Una representación posicional para números enteros que usa los dígitos binarios 0 y 1, en la que los valores representados por bits sucesivos son aditivos, comienzan con 1 y se multiplican por la potencia integral sucesiva de 2, excepto quizás para el bit con la posición más alta.

Lo interesante de esta redacción es que se contradice, porque la definición de "sistema de numeración binario puro" no permite una representación de signo / magnitud. Sí permite que el bit alto tenga, digamos, el valor -2 ^n-1 (complemento de dos) o - (2 ^n-1 -1) (complemento de uno). Pero no hay ningún valor para el bit alto que resulta en signo / magnitud.

De todos modos, mi "implementación hipotética" no califica como "binario puro" bajo esta definición, por lo que se descarta.

Sin embargo, el hecho de que el bit alto sea especial significa que podemos imaginarlo contribuyendo con cualquier valor: un valor positivo pequeño, un valor positivo enorme, un valor negativo pequeño o un valor negativo enorme. (Si el bit de signo puede contribuir - (2 ^n-1 -1), ¿por qué no - (2 ^n-1 -2)? Etc.)

Entonces, imaginemos una representación de entero con signo que asigna un valor extravagante al bit de "signo".

Un pequeño valor positivo para el bit de signo daría como resultado un rango positivo para int(posiblemente tan grande como unsigned), y el código de hvd lo maneja bien.

Un valor positivo enorme para el bit de signo daría como resultado intun máximo mayor que unsigned, lo cual está prohibido.

Un valor negativo enorme para el bit de signo daría como resultado la intrepresentación de un rango de valores no contiguo, y otra redacción en la especificación lo excluye.

Finalmente, ¿qué tal un bit de signo que aporta una pequeña cantidad negativa? ¿Podríamos hacer que un 1 en el "bit de signo" contribuya, digamos, -37 al valor del int? Entonces, ¿INT_MAX sería (digamos) 2 ³¹ -1 e INT_MIN sería -37?

Esto daría como resultado que algunos números tuvieran dos representaciones ... Pero el complemento a unos da dos representaciones a cero, y eso está permitido según el "Ejemplo". En ninguna parte la especificación dice que cero es el único entero que podría tener dos representaciones. Así que creo que esta nueva hipótesis está permitida por la especificación.

De hecho, cualquier valor negativo desde -1 hasta -INT_MAX-1parece estar permitido como valor para el "bit de signo", pero nada más pequeño (para que el rango no sea contiguo). En otras palabras, INT_MINpuede ser cualquier valor entre -INT_MAX-1-1.

Ahora, ¿adivinen qué? Para que la segunda conversión en el código de hvd evite el comportamiento definido por la implementación, solo necesitamos x - (unsigned)INT_MINmenor o igual a INT_MAX. Acabamos de mostrar INT_MINes al menos -INT_MAX-1. Obviamente, xes como mucho UINT_MAX. Lanzar un número negativo a unsigned es lo mismo que sumar UINT_MAX+1. Ponlo todo junto:

x - (unsigned)INT_MIN <= INT_MAX

si y solo 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

Eso último es lo que acabamos de mostrar, así que incluso en este caso perverso, el código realmente funciona.

Eso agota todas las posibilidades, poniendo fin a este ejercicio sumamente académico.

En pocas palabras: hay un comportamiento muy subespecificado para los enteros con signo en C89 / C90 que fueron heredados por C ++ 98 / C ++ 03. Está corregido en C99, y C ++ 11 hereda indirectamente la corrección al incorporarlo <limits.h>de C99. Pero incluso C ++ 11 conserva la redacción autocontradictoria de "representación binaria pura" ...

Este código se basa solo en el comportamiento, exigido por la especificación, por lo que el requisito (a) se cumple fácilmente:

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;
}

No es tan fácil con el requisito (b). Esto se compila en un no-op con gcc 4.6.3 (-Os, -O2, -O3) y con clang 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 se niega a optimizar esto. Y no tengo información sobre Visual C.

La respuesta original resolvió el problema solo para unsigned=>int . ¿Qué pasa si queremos resolver el problema general de "algún tipo sin firmar" a su tipo con signo correspondiente? Además, la respuesta original fue excelente para citar secciones del estándar y analizar algunos casos de esquina, pero realmente no me ayudó a tener una idea de por qué funcionó, por lo que esta respuesta intentará brindar una base conceptual sólida. Esta respuesta intentará ayudar a explicar "por qué" y utilizará las características modernas de C ++ para intentar simplificar el código.

C ++ 20 respuesta

El problema se ha simplificado drásticamente con P0907: los enteros firmados son el complemento de dos y la redacción final P1236 que se votó en el estándar C ++ 20. Ahora, la respuesta es lo más simple posible:

template<std::unsigned_integral T>
constexpr auto cast_to_signed_integer(T const value) {
    return static_cast<std::make_signed_t<T>>(value);
}

Eso es. Un static_cast(o conversión de estilo C) finalmente está garantizado para hacer lo que necesita para esta pregunta, y lo que muchos programadores pensó que siempre lo hacía.

C ++ 17 respuesta

En C ++ 17, las cosas son mucho más complicadas. Tenemos que tratar con tres posibles representaciones enteras (complemento a dos, complemento a uno y signo-magnitud). Incluso en el caso de que sepamos que debe ser un complemento a dos porque verificamos el rango de valores posibles, la conversión de un valor fuera del rango del entero con signo a ese entero con signo todavía nos da un resultado definido por la implementación. Tenemos que usar trucos como hemos visto en otras respuestas.

Primero, aquí está el código sobre cómo resolver el problema de forma genérica:

template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
constexpr auto cast_to_signed_integer(T const value) {
    using result = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<T>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<result>(value);
    } else {
        using promoted_unsigned = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
        using promoted_signed = std::make_signed_t<promoted_unsigned>;
        constexpr auto shift_by_window = [](auto x) {
            // static_cast to avoid conversion warning
            return x - static_cast<decltype(x)>(result_limits::max()) - 1;
        };
        return static_cast<result>(
            shift_by_window( // shift values from common range to negative range
                static_cast<promoted_signed>(
                    shift_by_window( // shift large values into common range
                        static_cast<promoted_unsigned>(value) // cast to avoid promotion to int
                    )
                )
            )
        );
    }
}

Esto tiene algunas conversiones más que la respuesta aceptada, y eso es para garantizar que no haya advertencias de discrepancia firmadas / sin firmar de su compilador y para manejar adecuadamente las reglas de promoción de enteros.

Primero tenemos un caso especial para sistemas que no son complemento a dos (y por lo tanto debemos manejar el valor máximo posible especialmente porque no tiene nada que mapear). Después de eso, llegamos al algoritmo real.

La segunda condición de nivel superior es sencilla: sabemos que el valor es menor o igual que el valor máximo, por lo que encaja en el tipo de resultado. La tercera condición es un poco más complicada incluso con los comentarios, por lo que algunos ejemplos probablemente ayudarían a comprender por qué es necesaria cada declaración.

Base conceptual: la recta numérica

Primero, ¿cuál es este windowconcepto? Considere la siguiente recta numérica:

   |   signed   |
<.........................>
          |  unsigned  |

Resulta que para los enteros en complemento a dos, puede dividir el subconjunto de la recta numérica al que puede llegar cualquier tipo en tres categorías de igual tamaño:

- => signed only
= => both
+ => unsigned only

<..-------=======+++++++..>

Esto se puede probar fácilmente considerando la representación. Un entero sin signo comienza en 0y usa todos los bits para incrementar el valor en potencias de 2. Un entero con signo es exactamente igual para todos los bits excepto el bit de signo, que vale en -(2^position)lugar de 2^position. Esto significa que para todos los n - 1bits, representan los mismos valores. Entonces, los enteros sin signo tienen un bit normal más, que duplica el número total de valores (en otras palabras, hay tantos valores con ese bit establecido como sin él). La misma lógica se aplica a los enteros con signo, excepto que todos los valores con ese conjunto de bits son negativos.

Las otras dos representaciones de enteros legales, complemento a uno y magnitud de signo, tienen todos los mismos valores que los enteros en complemento a dos, excepto uno: el valor más negativo. C ++ define todo sobre los tipos de enteros, excepto reinterpret_cast(y C ++ 20 std::bit_cast), en términos del rango de valores representables, no en términos de representación de bits. Esto significa que nuestro análisis se mantendrá para cada una de estas tres representaciones siempre que nunca intentemos crear la representación trampa. El valor sin signo que se correlacionaría con este valor perdido es bastante desafortunado: el que está justo en el medio de los valores sin firmar. Afortunadamente, nuestra primera condición verifica (en tiempo de compilación) si existe tal representación y luego la maneja especialmente con una verificación en tiempo de ejecución.

La primera condición maneja el caso en el que estamos en la =sección, lo que significa que estamos en la región superpuesta donde los valores en uno se pueden representar en el otro sin cambios. La shift_by_windowfunción en el código mueve todos los valores hacia abajo por el tamaño de cada uno de estos segmentos (tenemos que restar el valor máximo y luego restar 1 para evitar problemas de desbordamiento aritmético). Si estamos fuera de esa región (estamos en la +región), necesitamos saltar un tamaño de ventana hacia abajo. Esto nos coloca en el rango de superposición, lo que significa que podemos convertir de forma segura de sin firmar a firmado porque no hay ningún cambio en el valor. Sin embargo, todavía no hemos terminado porque hemos asignado dos valores sin firmar a cada valor firmado. Por lo tanto, debemos cambiar a la siguiente ventana (la- region) para que tengamos un mapeo único nuevamente.

Ahora, ¿esto nos da un resultado congruente mod UINT_MAX + 1, como se solicita en la pregunta? UINT_MAX + 1es equivalente a 2^n, donde nes el número de bits en la representación del valor. El valor que usamos para el tamaño de nuestra ventana es igual a 2^(n - 1)(el índice final en una secuencia de valores es uno menos que el tamaño). Restamos ese valor dos veces, lo que significa que restamos 2 * 2^(n - 1)cuál es igual a 2^n. Sumar y restar no xes una operación en el mod aritmético x, por lo que no hemos afectado el mod de valor original 2^n.

Manejo adecuado de promociones de enteros

Porque esta es una función genérica y no justa inty unsigned, también tenemos que preocuparnos por las reglas integrales de promoción. Hay dos casos posiblemente interesantes: uno en el que shortes menor que inty otro en el que shortes del mismo tamaño que int.

Ejemplo: shortmenor queint

Si shortes más pequeño que int(común en las plataformas modernas), entonces también sabemos que unsigned shortpuede caber en an int, lo que significa que cualquier operación en él realmente sucederá int, por lo que enviamos explícitamente al tipo promocionado para evitar esto. Nuestra declaración final es bastante abstracta y se vuelve más fácil de entender si la sustituimos por valores reales. Para nuestro primer caso interesante, sin pérdida de generalidad, consideremos uno de 16 bits shorty uno de 17 bits int(que todavía está permitido bajo las nuevas reglas, y solo significaría que al menos uno de esos dos tipos de enteros tiene algunos bits de relleno ):

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int17_t>(
            shift_by_window(
                static_cast<uint17_t>(value)
            )
        )
    )
);

Resolviendo el mayor valor posible sin firmar de 16 bits

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return int16_t(
    shift_by_window(
        int17_t(
            shift_by_window(
                uint17_t(65535)
            )
        )
    )
);

Simplifica a

return int16_t(
    int17_t(
        uint17_t(65535) - uint17_t(32767) - 1
    ) -
    int17_t(32767) -
    1
);

Simplifica a

return int16_t(
    int17_t(uint17_t(32767)) -
    int17_t(32767) -
    1
);

Simplifica a

return int16_t(
    int17_t(32767) -
    int17_t(32767) -
    1
);

Simplifica a

return int16_t(-1);

Ponemos el mayor número posible sin firmar y regresamos -1, ¡éxito!

Ejemplo: shortmismo tamaño queint

Si shortes del mismo tamaño que int(poco común en las plataformas modernas), la regla de promoción integral es ligeramente diferente. En este caso, shortpromueve inty unsigned shortpromueve a unsigned. Afortunadamente, enviamos explícitamente cada resultado al tipo en el que queremos hacer el cálculo, por lo que terminamos sin promociones problemáticas. Sin pérdida de generalidad, consideremos 16 bits shorty 16 bits int:

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int16_t>(
            shift_by_window(
                static_cast<uint16_t>(value)
            )
        )
    )
);

Resolviendo el mayor valor posible sin firmar de 16 bits

auto x = int16_t(
    uint16_t(65535) - uint16_t(32767) - 1
);
return int16_t(
    x - int16_t(32767) - 1
);

Simplifica a

return int16_t(
    int16_t(32767) - int16_t(32767) - 1
);

Simplifica a

return int16_t(-1);

Ponemos el mayor número posible sin firmar y regresamos -1, ¡éxito!

¿Y si sólo se preocupan por inty unsignedy no se preocupan por las advertencias, al igual que la pregunta original?

constexpr int cast_to_signed_integer(unsigned const value) {
    using result_limits = std::numeric_limits<int>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<unsigned>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<int>(value);
    } else {
        constexpr int window = result_limits::min();
        return static_cast<int>(value + window) + window;
    }
}

Verlo en vivo

https://godbolt.org/z/74hY81

Aquí vemos que clang, gcc e icc no generan código para casty cast_to_signed_integer_basicen-O2 y -O3, y MSVC no genera código en /O2, por lo que la solución es óptima.

Puede decirle explícitamente al compilador lo que quiere hacer:

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);
  }
}

Se compila con gcc 4.7.2for x86_64-linux( g++ -O -S test.cpp) para

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

Si xes nuestro aporte ...

Si x > INT_MAX, queremos encontrar una constante ktal que 0< x - k*INT_MAX< INT_MAX.

Esto es fácil - unsigned int k = x / INT_MAX;. Entonces, dejaunsigned int x2 = x - k*INT_MAX;

Ahora podemos lanzar x2de intforma segura. Dejarint x3 = static_cast<int>(x2);

Ahora queremos restar algo como UINT_MAX - k * INT_MAX + 1de x3, sik > 0 .

Ahora, en un sistema de complemento a 2, siempre que x > INT_MAXesto funcione para:

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

Tenga en cuenta que UINT_MAX+1es cero en C ++ garantizado, la conversión a int fue un error, y restamosk*INT_MAX luego lo volvimos a agregar al "mismo valor". ¡Así que un optimizador aceptable debería poder borrar todas esas tonterías!

Eso deja el problema de x > INT_MAXo no. Bueno, creamos 2 ramas, una con x > INT_MAXy otra sin. El que no tiene hace un reparto estrecho, que el compilador optimiza a un noop. El que tiene ... hace un noop después de que finaliza el optimizador. El optimizador inteligente detecta ambas ramas en la misma cosa y deja caer la rama.

Problemas: si UINT_MAXes realmente grande en relación con INT_MAX, es posible que lo anterior no funcione. Lo asumo k*INT_MAX <= UINT_MAX+1implícitamente.

Probablemente podríamos atacar esto con algunas enumeraciones como:

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

que funcionan a 2 y 1 en un sistema de complemento a 2, creo (¿estamos garantizados para que las matemáticas funcionen? Eso es complicado ...), y hacen una lógica basada en estos que se optimizan fácilmente en sistemas de complemento que no son de 2 ...

Esto también abre el caso de excepción. Solo es posible si UINT_MAX es mucho más grande que (INT_MIN-INT_MAX), por lo que puede poner su código de excepción en un bloque if haciendo exactamente esa pregunta de alguna manera, y no lo ralentizará en un sistema tradicional.

No estoy exactamente seguro de cómo construir esas constantes en tiempo de compilación para lidiar correctamente con eso.

std::numeric_limits<int>::is_moduloes una constante de tiempo de compilación. para que pueda usarlo para la especialización de plantillas. problema resuelto, al menos si el compilador funciona junto con la inserción.

#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;
}

Creo que el tipo int tiene al menos dos bytes, por lo que INT_MIN e INT_MAX pueden cambiar en diferentes plataformas.

Tipos fundamentales

≤climits≥ encabezado

Mi dinero está en usar memcpy. Cualquier compilador decente sabe optimizarlo:

#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;
}

Para mí (Xcode 8.3.2, Apple LLVM 8.1, -O3), eso produce:

_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