¿Por qué se define el comportamiento de desbordamiento de enteros sin signo pero no el desbordamiento de enteros con signo?

210

El desbordamiento de enteros sin signo está bien definido por los estándares C y C ++. Por ejemplo, el estándar C99 ( §6.2.5/9) establece

Un cómputo que involucra operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

Sin embargo, ambos estándares establecen que el desbordamiento de enteros con signo es un comportamiento indefinido. De nuevo, desde el estándar C99 ( §3.4.3/1)

Un ejemplo de comportamiento indefinido es el comportamiento en el desbordamiento de enteros

¿Existe una razón histórica o (¡incluso mejor!) Técnica para esta discrepancia?

c++ c undefined-behavior integer-overflow Anthony Vallée-Dubois
fuente
50
Probablemente porque hay más de una forma de representar enteros con signo. De qué manera no se especifica en el estándar, al menos no en C ++.
juanchopanza
Enlace útil: en.wikipedia.org/wiki/Signed_number_representations
Robᵩ
77
Lo que dijo juanchopanza tiene sentido. Según tengo entendido, el estándar C original en gran parte codificó la práctica existente. Si todas las implementaciones en ese momento acordaron lo que debe hacer el "desbordamiento" sin firmar, esa es una buena razón para estandarizarlo. No estuvieron de acuerdo en lo que debería hacer el desbordamiento firmado, por lo que no entró en el estándar.
2
@DavidElliman La envoltura sin firmar en la adición también es fácilmente detectable ( if (a + b < a)). El desbordamiento en la multiplicación es difícil para los tipos con signo y sin signo.
55
@DavidElliman: No es solo una cuestión de si puedes detectarlo, sino cuál es el resultado. En una implementación de signo + valor MAX_INT+1 == -0, mientras que en un complemento de dos seríaINT_MIN
David Rodríguez - dribeas

Respuestas:

163

La razón histórica es que la mayoría de las implementaciones de C (compiladores) simplemente usaron cualquier comportamiento de desbordamiento que fuera más fácil de implementar con la representación entera que usaban. Las implementaciones de C generalmente usaban la misma representación utilizada por la CPU, por lo que el comportamiento de desbordamiento siguió a la representación de enteros utilizada por la CPU.

En la práctica, solo las representaciones de los valores con signo pueden diferir según la implementación: el complemento de uno, el complemento de dos, la magnitud del signo. Para un tipo sin signo, no hay razón para que el estándar permita la variación porque solo hay una representación binaria obvia (el estándar solo permite la representación binaria).

Citas relevantes:

C99 6.2.6.1:3 :

Los valores almacenados en campos de bits sin signo y objetos de tipo char sin signo se representarán utilizando una notación binaria pura.

C99 6.2.6.2:2 :

Si el bit de signo es uno, el valor se modificará de una de las siguientes maneras:

- el valor correspondiente con el bit de signo 0 se niega ( signo y magnitud );

- el bit de signo tiene el valor - (2 N ) ( complemento de dos );

- el bit de signo tiene el valor - (2 N - 1) ( complemento de uno ).

Hoy en día, todos los procesadores usan la representación del complemento de dos, pero el desbordamiento aritmético con signo permanece indefinido y los fabricantes de compiladores quieren que permanezca indefinido porque usan esta indefinición para ayudar con la optimización. Vea, por ejemplo, esta publicación de blog de Ian Lance Taylor o esta queja de Agner Fog, y las respuestas a su informe de error.

Pascal Cuoq
fuente
66
La nota importante aquí, sin embargo, es que sigue habiendo no hay arquitecturas en el mundo moderno el uso de otros complemento a 2 con signo aritmético nada. Que los estándares de lenguaje aún permitan la implementación, por ejemplo, en un PDP-1 es un artefacto histórico puro.
Andy Ross el
9
@AndyRoss, pero todavía hay sistemas (compiladores OS +, ciertamente con una historia antigua) con su complemento y nuevas versiones a partir de 2013. Un ejemplo: OS 2200.
ouah
3
@Andy Ross, ¿consideraría que "no hay arquitecturas ... usando algo que no sea el complemento de 2 ..." hoy incluye toda la gama de DSP y procesadores integrados?
chux - Restablece a Mónica el
11
@AndyRoss: Si bien hay arquitecturas "no" que usan algo que no sea el complemento 2s (para alguna definición de "no"), definitivamente hay arquitecturas DSP que usan aritmética saturada para enteros con signo.
Stephen Canon
10
La aritmética con signo saturado definitivamente cumple con el estándar. Por supuesto, las instrucciones de ajuste deben usarse para la aritmética sin signo, pero el compilador siempre tiene la información para saber si se está haciendo aritmética sin signo o con signo, por lo que ciertamente puede elegir las instrucciones de manera adecuada.
caf
15

Aparte de la buena respuesta de Pascal (que estoy seguro es la motivación principal), también es posible que algunos procesadores causen una excepción en el desbordamiento de enteros con signo, lo que, por supuesto, causaría problemas si el compilador tuviera que "organizar otro comportamiento" ( por ejemplo, use instrucciones adicionales para verificar el desbordamiento potencial y calcular de manera diferente en ese caso).

También vale la pena señalar que "comportamiento indefinido" no significa "no funciona". Significa que la implementación puede hacer lo que quiera en esa situación. Esto incluye hacer "lo correcto", así como "llamar a la policía" o "estrellarse". La mayoría de los compiladores, cuando sea posible, elegirán "hacer lo correcto", suponiendo que sea relativamente fácil de definir (en este caso, lo es). Sin embargo, si tiene desbordamientos en los cálculos, es importante comprender lo que realmente da como resultado, y que el compilador PUEDE hacer algo diferente a lo que espera (y que esto puede depender mucho de la versión del compilador, la configuración de optimización, etc.) .

Mats Petersson
fuente
23
Sin embargo, los compiladores no quieren que confíes en ellos para hacer lo correcto, y la mayoría de ellos te lo mostrarán tan pronto como compiles int f(int x) { return x+1>x; }con optimización. GCC e ICC hacen, con las opciones predeterminadas, optimizar lo anterior para return 1;.
Pascal Cuoq
1
Para ver un programa de ejemplo que ofrece resultados diferentes cuando se enfrenta a un intdesbordamiento dependiendo de los niveles de optimización, consulte ideone.com/cki8nM. Creo que esto demuestra que su respuesta da malos consejos.
Magnus Hoff el
He modificado esa parte un poco.
Mats Petersson el
Si una C proporcionara un medio para declarar un entero "envolviendo el complemento de dos firmado", ninguna plataforma que pueda ejecutar C debería tener muchos problemas para soportarlo, al menos moderadamente eficientemente. La sobrecarga adicional sería suficiente para que el código no use un tipo de este tipo cuando no se requiera un comportamiento de ajuste, pero la mayoría de las operaciones en los enteros complementarios de dos son idénticas a las de los enteros sin signo, excepto las comparaciones y promociones.
supercat
1
Los valores negativos deben existir y "funcionar" para que el compilador funcione correctamente. Por supuesto, es completamente posible evitar la falta de valores con signo dentro de un procesador y usar valores sin signo, ya sea como complemento o como complemento, lo que sea más sentido basado en lo que es el conjunto de instrucciones. Por lo general, sería mucho más lento hacer esto que tener soporte de hardware para él, pero no es diferente de los procesadores que no admiten punto flotante en hardware o similar, solo agrega mucho código adicional.
Mats Petersson
10

En primer lugar, tenga en cuenta que C11 3.4.3, como todos los ejemplos y notas al pie, no es un texto normativo y, por lo tanto, no es relevante para citar.

El texto relevante que establece que el desbordamiento de enteros y flotantes es un comportamiento indefinido es el siguiente:

C11 6.5 / 5

Si se produce una condición excepcional durante la evaluación de una expresión (es decir, si el resultado no está matemáticamente definido o no está en el rango de valores representables para su tipo), el comportamiento es indefinido.

Aquí se puede encontrar una aclaración sobre el comportamiento de los tipos enteros sin signo:

C11 6.2.5 / 9

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. Un cálculo que involucra operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero resultante sin signo se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

Esto hace que los tipos enteros sin signo sean un caso especial.

También tenga en cuenta que hay una excepción si cualquier tipo se convierte en un tipo con signo y el valor anterior ya no se puede representar. El comportamiento se define simplemente por implementación, aunque se puede generar una señal.

C11 6.3.1.3

6.3.1.3 Enteros con y sin signo

Cuando un valor con tipo entero se convierte en otro tipo entero distinto de _Bool, si el valor puede ser representado por el nuevo tipo, no se modifica.

De lo contrario, si el nuevo tipo no tiene signo, el valor se convierte agregando o restando repetidamente uno más que el valor máximo que se puede representar en el nuevo tipo hasta que el valor esté en el rango del nuevo tipo.

De lo contrario, el nuevo tipo se firma y el valor no se puede representar en él; o bien el resultado está definido por la implementación o se genera una señal definida por la implementación.

Lundin
fuente
6

Además de los otros problemas mencionados, tener un ajuste matemático sin signo hace que los tipos enteros sin signo se comporten como grupos algebraicos abstractos (lo que significa que, entre otras cosas, para cualquier par de valores Xy Y, existirá algún otro valor Zque X+Z, si se emite correctamente , igual Yy Y-Zvoluntad, si se lanza correctamente, igualX) Si los valores sin signo eran simplemente tipos de ubicación de almacenamiento y no tipos de expresión intermedia (por ejemplo, si no hubiera un equivalente sin signo del tipo entero más grande, y las operaciones aritméticas en tipos sin signo se comportaban como si primero se convirtieran en tipos con signo más grandes, entonces no no sería tan necesario un comportamiento de ajuste definido, pero es difícil hacer cálculos en un tipo que no tiene, por ejemplo, un inverso aditivo.

Esto ayuda en situaciones donde el comportamiento envolvente es realmente útil, por ejemplo, con números de secuencia TCP o ciertos algoritmos, como el cálculo de hash. También puede ayudar en situaciones donde es necesario detectar el desbordamiento, ya que realizar cálculos y verificar si se desbordaron a menudo es más fácil que verificar de antemano si se desbordarían, especialmente si los cálculos involucran el tipo entero más grande disponible.

Super gato
fuente
No entiendo exactamente: ¿por qué ayuda tener un inverso aditivo? Realmente no puedo pensar en ninguna situación en la que el comportamiento de desbordamiento sea realmente útil ...
sleske
@sleske: Usar el decimal para la legibilidad humana, si un medidor de energía lee 0003 y la lectura anterior fue 9995, ¿eso significa que se usaron -9992 unidades de energía o que se usaron 0008 unidades de energía? Tener un rendimiento 0003-9995 0008 facilita el cálculo del último resultado. Hacer que rinda -9992 lo haría un poco más incómodo. Sin embargo, al no poder hacerlo, sería necesario comparar 0003 con 9995, notar que es menor, hacer la resta inversa, restar ese resultado de 9999 y sumar 1.
supercat
@sleske: También es muy útil para humanos y compiladores poder aplicar las leyes asociativas, distributivas y conmutativas de la aritmética para reescribir expresiones y simplificarlas; por ejemplo, si la expresión a+b-cse calcula dentro de un ciclo, pero by ces constante dentro de ese ciclo, puede ser útil mover el cálculo (b-c)fuera del ciclo, pero hacerlo requeriría, entre otras cosas, (b-c)un valor que, cuando se agrega a a, rendirá a+b-c, lo que a su vez requiere que ctenga un inverso aditivo.
supercat
: Gracias por las explicaciones. Si lo entiendo correctamente, todos sus ejemplos suponen que realmente desea manejar el desbordamiento. En la mayoría de los casos que he encontrado, el desbordamiento no es deseable y desea evitarlo, porque el resultado de un cálculo con desbordamiento no es útil. Por ejemplo, para el medidor de energía, es probable que desee utilizar un tipo que nunca se produzca un desbordamiento.
sleske
1
... de modo que sea (a+b)-cigual a+(b-c)o no que el valor aritmético de b-csea ​​representable dentro del tipo, la sustitución será válida independientemente del posible rango de valores para (b-c).
supercat
1

Quizás otra razón por la cual se define la aritmética sin signo es porque los números sin signo forman números enteros módulo 2 ^ n, donde n es el ancho del número sin signo. Los números sin signo son simplemente números enteros representados usando dígitos binarios en lugar de dígitos decimales. Realización de las operaciones estándar en un sistema de módulo se entiende bien.

La cita del OP se refiere a este hecho, pero también destaca el hecho de que solo hay una forma lógica, inequívoca, de representar enteros sin signo en binario. Por el contrario, los números con signo se representan con mayor frecuencia utilizando el complemento de dos, pero son posibles otras opciones como se describe en el estándar (sección 6.2.6.2).

La representación del complemento a dos permite que ciertas operaciones tengan más sentido en formato binario. Por ejemplo, incrementar números negativos es lo mismo que para números positivos (espere bajo condiciones de desbordamiento). Algunas operaciones a nivel de máquina pueden ser las mismas para números con y sin signo. Sin embargo, al interpretar el resultado de esas operaciones, algunos casos no tienen sentido: desbordamiento positivo y negativo. Además, los resultados de desbordamiento difieren según la representación firmada subyacente.

enés
fuente
Para que una estructura sea un campo, cada elemento de la estructura que no sea la identidad aditiva debe tener un inverso multiplicativo. Una estructura de enteros congruentes mod N será un campo solo cuando N es uno o primo [un campo degnerate cuando N == 1]. ¿Hay algo que sientas que me perdí en mi respuesta?
supercat
Tienes razón. Me confundí con los módulos de poder principal. Respuesta original editada.
yth
Adicional confuso aquí es que no es un campo de orden 2 ^ n, es simplemente no anillo isomorfo a los enteros módulo 2 ^ n.
Kevin Ventullo
Y, 2 ^ 31-1 es un Mersenne Prime (pero 2 ^ 63-1 no es primo). Por lo tanto, mi idea original se arruinó. Además, los tamaños enteros eran diferentes en el día. Entonces, mi idea era revisionista en el mejor de los casos.
yth
El hecho de que los enteros sin signo formen un anillo (no un campo), tomar la porción de orden inferior también produce un anillo, y realizar operaciones sobre el valor completo y luego truncar se comportará de manera equivalente a realizar las operaciones solo en la porción inferior. casi seguramente consideraciones.
supercat