c++ - Elenco eficiente sin signo a firma evitando el comportamiento definido por la implementación
language-lawyer (8)
Quiero definir una función que toma un unsigned int como argumento y devuelve un módulo int 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 desde sin signo a los valores firmados por más de INT_MAX está definida por la implementación.
Quiero implementar esto de manera que (a) solo se base en el comportamiento ordenado por la especificación; y (b) se compila en una operación no operativa en cualquier máquina moderna y optimiza el compilador.
En cuanto a máquinas extrañas ... Si no hay un módulo congruente con signo UINT_MAX + 1 en el int sin signo, digamos que deseo lanzar una excepción. Si hay más de uno (no estoy seguro de que esto 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 descubrirlo y optimizarlo en ese momento.
Ahora, este segundo intento es bastante cercano a lo que quiero. Aunque el lanzamiento a int está definido por la implementación para algunas entradas, la conversión de nuevo a unsigned está garantizada por el estándar para preservar el módulo de valor UINT_MAX + 1. Entonces, el condicional verifica exactamente lo que quiero, y se compilará en nada en cualquier sistema que pueda encontrar.
Sin embargo ... todavía estoy volviendo a int sin verificar primero si invocará un comportamiento definido por la implementación. En algún sistema hipotético en 2050 podría hacer quién sabe qué. Entonces digamos que quiero evitar eso.
Pregunta: ¿Cómo debería ser mi "tercer intento"?
Para recapitular, quiero:
- Enviar desde unsigned int a signed int
- Conservar el valor mod UINT_MAX + 1
- Invocar solo el comportamiento obligatorio estándar
- Compilar en un no-op en una típica máquina de dos en 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_MAXes igual a 32767 -
INT_MINes igual a -2 32 + 32768 -
UINT_MAXes igual a 2 32 - 1 - Aritmética en
intes modulo 2 32 (en el rangoINT_MINaINT_MAX) -
std::numeric_limits<int>::is_moduloes verdadero - Casting unsigned
nto int conserva el valor de 0 <= n <= 32767 y produce cero de lo contrario
En esta implementación hipotética, hay exactamente un valor int congruente (mod UINT_MAX + 1) para cada valor unsigned . Entonces mi pregunta estaría bien definida.
Yo afirmo que esta implementación hipotética de C ++ cumple completamente con las especificaciones C ++ 98, C ++ 03 y C ++ 11. Admito que no he memorizado cada palabra de todos ellos ... Pero creo que he leído detenidamente las secciones pertinentes. Entonces, si quiere que acepte su respuesta, debe (a) citar una especificación que descarta 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 "invocar solo el comportamiento obligatorio estándar" significa, por definición.
Por cierto, tenga en cuenta que std::numeric_limits<int>::is_modulo es completamente inútil aquí por varias razones. Por un lado, puede ser true incluso si las conversiones sin signo a firma no funcionan para valores grandes sin firmar. Por otro lado, puede ser true incluso en los sistemas de complemento de uno o magnitud de signo, si la aritmética es simplemente un módulo de todo el rango de enteros. 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 la C. moderna. Los estándares C99 y C11 son muy específicos sobre la representación de enteros con signo; de hecho, solo permiten el complemento a dos, el complemento a uno y la magnitud de signo (sección 6.2.6.2 párrafo (2);).
Pero C ++ no es C. Como resultado, este hecho se encuentra en el corazón de mi pregunta.
El estándar original C ++ 98 se basó en el C89 mucho más antiguo, que dice (sección 3.1.2.5):
Para cada uno de los tipos de entero con signo, existe un tipo de entero sin signo correspondiente (pero diferente) (designado con la palabra clave sin signo) que utiliza 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 entero con signo es un subrango del tipo entero sin signo correspondiente, y la representación del mismo valor en cada tipo es la misma.
C89 no dice nada acerca de tener solo un bit de signo o solo permitir twos-complemento / ones-complemento / signo-magnitud.
El estándar C ++ 98 adoptó este lenguaje casi textualmente (sección 3.9.1 párrafo (3)):
Para cada uno de los tipos enteros con signo, existe un tipo 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) que el tipo entero con signo correspondiente; es decir, cada tipo de entero con signo tiene la misma representación de objeto que su tipo de entero sin signo correspondiente. El rango de valores no negativos de un tipo entero con signo es un subrango del tipo entero sin signo correspondiente, y la representación del valor de cada tipo firmado / no firmado 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 de entero con signo a cualquier especificación C, por lo que yo sé. Y no hay nada que obligue a un solo signo 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.
Por lo tanto, nuevamente reclamo que INT_MAX = 32767 con INT_MIN = -2 32 +32768 está permitido. Si su respuesta asume lo contrario, es incorrecta a menos que cite un estándar de C ++ que demuestre que estoy equivocado.
Ampliando la respuesta del usuario71404:
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 promoción, INT_MIN se convierte en unsigned ), entonces x - INT_MIN <= INT_MAX , por lo que no tendrá ningún desbordamiento.
Si eso no es obvio, eche un vistazo a la afirmación "If x >= -4u , then x + 4 <= 3 ", Y tenga en cuenta que INT_MAX será igual a, al menos, el 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 declaraciones de return pueden compilarse para el mismo código, y eliminar el primer cheque 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 32 + 32768
no es posible, por lo que no necesita una consideración especial. INT_MIN será igual a -INT_MAX , o a -INT_MAX - 1 . Esto se sigue de la representación de tipos enteros (6.2.6.2) de C, que requiere n bits para ser bits de valor, un bit para ser un bit de signo y solo permite una sola representación de captura (sin incluir representaciones que no son válidas debido a los bits de relleno) , es decir, aquel que representaría cero negativo / -INT_MAX - 1 . C ++ no permite representaciones enteras más allá de lo que C permite.
Actualización : aparentemente, el compilador de Microsoft no advierte que x > 10 y x >= 11 prueban lo mismo. Solo genera el código deseado si x >= INT_MIN se reemplaza por x > INT_MIN - 1u , que puede detectarse como la negación de x <= INT_MAX (en esta plataforma).
[Actualización del interrogador (Nemo), explicando 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 a esta solución, pero quiero capturar todos los detalles sangrientos por si a alguien le importa.
Comencemos con C ++ 11, sección 18.3.3:
La Tabla 31 describe el encabezado
<climits>....
Los contenidos son los mismos que el encabezado de la biblioteca estándar C
<limits.h>.
Aquí, "Estándar C" significa C99, cuya especificación restringe severamente la representación de los enteros con signo. Son como enteros sin signo, pero con un bit dedicado a "signo" y cero o más bits dedicados a "relleno". Los bits de relleno no contribuyen al valor del entero, y el bit de signo contribuye solo como complemento de dos, complemento de uno o magnitud de signo.
Como C ++ 11 hereda las macros <climits> de C99, INT_MIN es -INT_MAX o -INT_MAX-1, y se garantiza que el código de hvd funcionará. (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 los bloqueos firmados-> bloqueos sin signo funcionan, esta respuesta funciona bien).
C ++ 03 / C ++ 98 es más complicado. Utiliza la misma redacción para heredar <climits> de "Standard C", pero ahora "Standard 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 los tipos integrales definirán los valores mediante el uso de un sistema de numeración binario puro. (44) [ Ejemplo : esta Norma Internacional permite el complemento de 2, el complemento de 1 y las representaciones de magnitud firmada para los tipos integrales.]
La nota al pie (44) define "sistema de numeración binario puro":
Una representación posicional para enteros que usa los dígitos binarios 0 y 1, en los que los valores representados por bits sucesivos son aditivos, comienzan con 1 y se multiplican por la potencia integral sucesiva de 2, excepto tal vez para el bit con la posición más alta.
Lo interesante de esta redacción es que se contradice a sí misma, porque la definición de "sistema de numeración binario puro" no permite una representación de signo / magnitud. Permite que el bit alto tenga, por ejemplo, el valor -2 n-1 (complemento a dos) o - (2 n-1 -1) (complemento a uno). Pero no hay ningún valor para el bit alto que da como resultado signo / magnitud.
De todos modos, mi "implementación hipotética" no califica como "pura binaria" según esta definición, por lo que se descarta.
Sin embargo, el hecho de que el bit alto sea especial significa que podemos imaginar que aporta algún valor: un pequeño valor positivo, gran valor positivo, pequeño valor negativo o gran valor negativo. (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 extraño 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 se maneja muy bien.
Un gran valor positivo para el bit de signo daría como resultado que int tenga un tamaño máximo mayor que el unsigned , lo cual está prohibido.
Un gran valor negativo para el bit de signo daría como resultado que int representara un rango no contiguo de valores, y otra redacción en las reglas de especificación que salga.
Finalmente, ¿qué tal un bit de signo que aporta una pequeña cantidad negativa? ¿Podríamos tener un 1 en el "bit de signo" contribuir, digamos, -37 al valor de la int? ¿Entonces INT_MAX sería (digamos) 2 31 -1 e INT_MIN sería -37?
Esto daría como resultado que algunos números tengan dos representaciones ... Pero el complemento uno da dos representaciones a cero, y eso está permitido de acuerdo con el "Ejemplo". En ninguna parte la especificación dice que cero es el único entero que podría tener dos representaciones. Entonces creo que esta nueva hipotética está permitida por la especificación.
De hecho, cualquier valor negativo desde -1 hasta -INT_MAX-1 parece estar permitido como un valor para el "bit de signo", pero nada más pequeño (para que el rango no sea contiguo). En otras palabras, INT_MIN puede ser cualquier cosa desde -INT_MAX-1 a -1.
Ahora, adivina que? Para el segundo elenco en el código de hvd para evitar el comportamiento definido por la implementación, solo necesitamos x - (unsigned)INT_MIN menor o igual que INT_MAX . Acabamos de mostrar que INT_MIN es al menos -INT_MAX-1 . Obviamente, x es como máximo UINT_MAX . Convertir un número negativo en unsigned es lo mismo que agregar 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, por lo que incluso en este caso perverso, el código realmente funciona.
Eso agota todas las posibilidades, y así pone fin a este ejercicio extremadamente académico.
En pocas palabras: existe un comportamiento gravemente infraespecificado para los enteros con signo en C89 / C90 heredados por C ++ 98 / C ++ 03. Se fija en C99, y C ++ 11 hereda indirectamente la solución incorporando <limits.h> de C99. Pero incluso C ++ 11 conserva la fraseología de "representación binaria pura" contradictoria ...
Creo que el tipo int es al menos dos bytes, por lo que INT_MIN e INT_MAX pueden cambiar en diferentes plataformas.
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-operativo 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.
Esto es perfectamente compatible con las normas y se compilará en modo no operativo en MSVC / gcc.
int unsigned_to_signed(unsigned int n)
{
union UltimateCast
{
unsigned int In;
int Out;
} cast;
cast.In = n;
return cast.Out;
}
Para el código de llamada como:
volatile unsigned int i = 32167;
int main()
{
return unsigned_to_signed( i );
}
Tendremos esta salida de ensamblaje (g ++ -O3 -S):
__Z18unsigned_to_signedj:
movl 4(%esp), %eax
ret
_main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
call ___main
movl _i, %eax
leave
ret
.globl _i
.data
.align 4
_i:
.long 32167
Y declarar unsigned_to_signed() como rendimientos en inline :
_main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
call ___main
movl _i, %eax
leave
ret
.globl _i
.data
.align 4
_i:
.long 32167
Lo cual es un código bastante bueno.
Mi dinero está en usar memcpy. Cualquier compilador decente sabe para 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
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);
}
}
Compila con gcc 4.7.2 para x86_64-linux ( g++ -O -S test.cpp ) para
_Z18unsigned_to_signedj:
movl %edi, %eax
ret
Si x es nuestra entrada ...
Si x > INT_MAX , queremos encontrar una constante k tal que 0 < x - k*INT_MAX < INT_MAX .
Esto es fácil - unsigned int k = x / INT_MAX; . Entonces, deje unsigned int x2 = x - k*INT_MAX;
Ahora podemos convertir x2 a int forma segura. Deje int x3 = static_cast<int>(x2);
Ahora queremos restar algo como UINT_MAX - k * INT_MAX + 1 de x3 , si k > 0 .
Ahora, en un sistema complementario 2s, siempre que x > INT_MAX , esto 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+1 es cero en C ++ garantizado, la conversión a int fue un noop, y restamos k*INT_MAX luego lo agregamos de nuevo en "el mismo valor". ¡Entonces un optimizador aceptable debería poder borrar toda esa tontería!
Eso deja el problema de x > INT_MAX o no. Bueno, creamos 2 ramas, una con x > INT_MAX y otra sin. El que no tiene un estrecho, que el compilador optimiza para un noop. El que tiene ... hace un notop después de que el optimizador haya terminado. El optimizador inteligente realiza ambas ramas para hacer lo mismo y descarta la rama.
Problemas: si UINT_MAX es realmente grande en relación con INT_MAX , lo anterior podría no funcionar. Supongo que k*INT_MAX <= UINT_MAX+1 implícitamente.
Probablemente podríamos atacar esto con algunas enumeraciones como:
enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };
que funcionan con 2 y 1 en un sistema de complemento 2, creo (¿estamos garantizados para que las matemáticas funcionen? Eso es complicado ...), y hacemos una lógica basada en estos que optimizan fácilmente en sistemas complementarios que no sean 2s ...
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 preguntando exactamente esa pregunta de alguna manera, y no le ralentizará en un sistema tradicional.
No estoy exactamente seguro de cómo construir esas constantes en tiempo de compilación para tratar correctamente con eso.
std::numeric_limits<int>::is_modulo es una constante de tiempo de compilación. para que pueda usarlo para la especialización de plantilla. problema resuelto, al menos si el compilador juega junto con la alineació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;
}
EDITAR : reparó el código para evitar posibles trampas en máquinas no modulares-int (solo se sabe que existe una, a saber, las versiones configuradas arcaicamente de Unisys Clearpath). Para simplificar, esto se hace al no soportar el valor -2 n -1 donde n es el número de bits de valor int , en dicha máquina (es decir, en Clearpath). en la práctica, este valor tampoco será soportado por la máquina (es decir, con signo y magnitud o representación de complemento de 1).