Si un número es demasiado grande, ¿se pasa a la siguiente ubicación de memoria?

30

He estado revisando la programación en C y solo hay un par de cosas que me molestan.

Tomemos este código por ejemplo:

int myArray[5] = {1, 2, 2147483648, 4, 5};
int* ptr = myArray;
int i;
for(i=0; i<5; i++, ptr++)
    printf("\n Element %d holds %d at address %p", i, myArray[i], ptr);

Sé que un int puede tener un valor máximo de 2,147,483,647 positivo. Entonces, al pasar por eso, ¿se "desborda" a la siguiente dirección de memoria, lo que hace que el elemento 2 aparezca como "-2147483648" en esa dirección? Pero eso no tiene sentido porque en la salida todavía dice que la siguiente dirección tiene el valor 4, luego 5. Si el número se hubiera extendido a la siguiente dirección, ¿no cambiaría eso el valor almacenado en esa dirección? ?

Recuerdo vagamente de la programación en MIPS Assembly y viendo las direcciones cambiar los valores durante el programa paso a paso que los valores asignados a esas direcciones cambiarían.

A menos que recuerde incorrectamente, aquí hay otra pregunta: si el número asignado a una dirección específica es mayor que el tipo (como en myArray [2]), ¿no afecta a los valores almacenados en la dirección posterior?

Ejemplo: tenemos int myNum = 4 mil millones en la dirección 0x10010000. Por supuesto, myNum no puede almacenar 4 mil millones, por lo que aparece como un número negativo en esa dirección. A pesar de no poder almacenar este gran número, no tiene ningún efecto sobre el valor almacenado en la dirección posterior de 0x10010004. ¿Correcto?

Las direcciones de memoria solo tienen suficiente espacio para contener ciertos tamaños de números / caracteres, y si el tamaño supera el límite, entonces se representará de manera diferente (como tratar de almacenar 4 mil millones en el int pero aparecerá como un número negativo) y por lo que no tiene efecto en los números / caracteres almacenados en la siguiente dirección.

Lo siento si me fui por la borda. He tenido un gran pedo cerebral todo el día debido a esto.

achaparrado
fuente
10
Es posible que te confundas con desbordamientos de cadenas .
Robbie Dee
19
Tarea: Modificar una CPU sencilla de modo que lo hace el derrame. Verá que la lógica se vuelve mucho más compleja, todo por una "característica" que garantizaría agujeros de seguridad en todas partes sin ser útil en primer lugar.
phihag
44
Si necesita números realmente grandes, es posible tener una representación numérica que aumente la cantidad de memoria que utiliza para ajustar números grandes. El procesador en sí no puede hacer esto, y no es una característica del lenguaje C, pero una biblioteca puede implementarlo: una biblioteca C común es la biblioteca aritmética de precisión múltiple GNU . La biblioteca tiene que administrar la memoria para almacenar los números que tienen un costo de rendimiento además de la aritmética. Muchos idiomas tienen este tipo de cosas integradas (lo que no evita los costos).
Steve314
1
escribo una prueba simple, no soy un programador de C sino algo similar int c = INT.MAXINT; c+=1;y veo qué pasó con c.
JonH
2
@ JonH: El problema es que se desborda en Comportamiento indefinido. El compilador de CA puede detectar ese código y deducir que es un código inalcanzable porque se desborda incondicionalmente. Como el código inalcanzable no importa, se puede eliminar. Resultado final: no queda código.
MSalters

Respuestas:

48

No, no lo hace. En C, las variables tienen un conjunto fijo de direcciones de memoria para trabajar. Si está trabajando en un sistema con 4 bytes intsy establece una intvariable 2,147,483,647y luego agrega 1, la variable generalmente contendrá-2147483648 . (En la mayoría de los sistemas. El comportamiento en realidad no está definido). No se modificarán otras ubicaciones de memoria.

En esencia, el compilador no le permitirá asignar un valor que sea demasiado grande para el tipo. Esto generará un error del compilador. Si lo fuerza con un caso, el valor se truncará.

Visto de manera bit a bit, si el tipo solo puede almacenar 8 bits e intenta forzar el valor 1010101010101con un caso, terminará con los 8 bits inferiores, o01010101 .

En su ejemplo, independientemente de lo que haga myArray[2], myArray[3]contendrá '4'. No hay "derrame". Estás tratando de poner algo que tenga más de 4 bytes, simplemente cortará todo en el extremo superior, dejando los 4 bytes inferiores. En la mayoría de los sistemas, esto resultará en -2147483648.

Desde un punto de vista práctico, solo debes asegurarte de que esto nunca ocurra. Este tipo de desbordamientos a menudo resultan en defectos difíciles de resolver. En otras palabras, si cree que hay alguna posibilidad de que sus valores estén en miles de millones, no lo use int.

Gort the Robot
fuente
52
Si está trabajando en un sistema con entradas de 4 bytes, y establece una variable int en 2,147,483,647 y luego agrega 1, la variable contendrá -2147483648. => No , es Comportamiento indefinido , por lo que puede dar vueltas o hacer algo completamente diferente; He visto compiladores que optimizan las comprobaciones basadas en la ausencia de desbordamiento y obtuve bucles infinitos, por ejemplo ...
Matthieu M.
Lo siento, sí, tienes razón. Debería haber agregado un "generalmente" allí.
Gort the Robot
@MatthieuM desde una perspectiva de lenguaje , eso es cierto. En términos de ejecución en un sistema dado, que es de lo que estamos hablando aquí, es una tontería absoluta.
hobbs
@hobbs: El problema es que cuando los compiladores destruyen el programa debido a Comportamiento indefinido, ejecutar el programa realmente producirá un comportamiento inesperado, comparable en efecto a sobrescribir la memoria.
Matthieu M.
24

El desbordamiento de entero firmado es un comportamiento indefinido. Si esto sucede, su programa no es válido. No es necesario que el compilador verifique esto por usted, por lo que puede generar un ejecutable que parece hacer algo razonable, pero no hay garantía de que lo haga.

Sin embargo, el desbordamiento de entero sin signo está bien definido. Envolverá el módulo UINT_MAX + 1. La memoria no ocupada por su variable no se verá afectada.

Ver también https://stackoverflow.com/q/18195715/951890

Vaughn Cato
fuente
el desbordamiento de entero con signo está tan bien definido como el desbordamiento de entero sin signo. si la palabra tiene $ N $ bits, el límite superior del desbordamiento de entero con signo está en $$ 2 ^ {N-1} -1 $$ (donde se ajusta a $ -2 ^ {N-1} $) mientras que el el límite superior para el desbordamiento de entero sin signo está en $$ 2 ^ N - 1 $$ (donde se ajusta a $ 0 $). Los mismos mecanismos de suma y resta, el mismo tamaño del rango de números ($ 2 ^ N $) que se pueden representar. solo un límite diferente de desbordamiento.
Robert Bristow-Johnson
1
@ robertbristow-johnson: No según el estándar C.
Vaughn Cato
bueno, los estándares a veces son anacrónicos. Al observar la referencia SO, hay un comentario que lo golpea directamente: "Sin embargo, la nota importante aquí es que no quedan arquitecturas en el mundo moderno que utilicen otra cosa que no sea la aritmética con signo complementario de 2. Que los estándares de lenguaje aún permiten la implementación en, por ejemplo, un PDP-1 es un artefacto histórico puro. - Andy Ross 12 de agosto de 13 a las 20:12 "
Robert Bristow-Johnson
supongo que no está en el estándar C, pero supongo que podría haber una implementación en la que no se utiliza la aritmética binaria regular int. Supongo que podrían usar el código Gray o BCD o EBCDIC . No sé por qué alguien diseñaría hardware para hacer aritmética con código Gray o EBCDIC, pero, de nuevo, no sé por qué alguien haría unsignedcon binario y firmaría intcon algo que no sea el complemento de 2.
Robert Bristow-Johnson
14

Entonces, hay dos cosas aquí:

  • el nivel del lenguaje: ¿cuáles son las semánticas de C
  • el nivel de la máquina: cuáles son las semánticas del ensamblaje / CPU que usa

A nivel de idioma:

Cía:

  • desbordamiento y desbordamiento se definen como módulo aritmético para unsigned enteros , por lo tanto su valor "bucles"
  • desbordamiento y desbordamiento son comportamientos indefinidos para enteros con signo , por lo tanto, cualquier cosa puede suceder

Para aquellos que quieran un ejemplo de "lo que sea", he visto:

for (int i = 0; i >= 0; i++) {
    ...
}

convertirse en:

for (int i = 0; true; i++) {
    ...
}

y sí, esta es una transformación legítima.

Significa que, de hecho, existen riesgos potenciales de sobrescribir la memoria en el desbordamiento debido a alguna extraña transformación del compilador.

Nota: en el uso de Clang o gcc -fsanitize=undefineden Debug para activar el Desinfectante de Comportamiento Indefinido que abortará en el desbordamiento / desbordamiento de enteros firmados.

O significa que puede sobrescribir la memoria utilizando el resultado de la operación para indexar (sin marcar) en una matriz. Desafortunadamente, esto es mucho más probable en ausencia de detección de subflujo / desbordamiento.

Nota: en el uso de Clang o gcc -fsanitize=addressen Debug para activar el desinfectante de direcciones que abortará en el acceso fuera de los límites.


A nivel de máquina :

Realmente depende de las instrucciones de montaje y la CPU que use:

  • en x86, ADD usará 2 complementos en overflow / underflow, y establecerá OF (Overflow Flag)
  • en la futura CPU Mill, habrá 4 modos de desbordamiento diferentes para Add:
    • Módulo: módulo de 2 complementos
    • Trampa: se genera una trampa, deteniendo el cálculo
    • Saturar: el valor se atasca en min en desbordamiento o max en desbordamiento
    • Doble ancho: el resultado se genera en un registro de doble ancho

Tenga en cuenta que si las cosas suceden en los registros o en la memoria, en ningún caso la CPU sobrescribe la memoria en caso de desbordamiento.

Matthieu M.
fuente
¿Están firmados los últimos tres modos? (No importa para el primero, ya que es un complemento de 2).
Deduplicador
1
@Deduplicator: De acuerdo con la Introducción al modelo de programación de CPU Mill, existen diferentes códigos de operación para la suma firmada y la suma no firmada; Espero que ambos opcodes admitan los 4 modos (y puedan operar en varios bits de ancho y escalar / vectores). Por otra parte, es hardware de vapor por ahora;)
Matthieu M.
4

Para avanzar en la respuesta de @ StevenBurnap, la razón por la que esto sucede se debe a cómo funcionan las computadoras a nivel de máquina.

Su matriz se almacena en la memoria (por ejemplo, en la RAM). Cuando se realiza una operación aritmética, el valor en la memoria se copia en los registros de entrada del circuito que realiza la aritmética (ALU: Aritmetic Logic Unit ), la operación se lleva a cabo en los datos en los registros de entrada, produciendo un resultado en el registro de salida. Este resultado se copia nuevamente en la memoria en la dirección correcta en la memoria, dejando intactas otras áreas de la memoria.

Pharap
fuente
4

Primero (suponiendo que el estándar C99), es posible que desee incluir <stdint.h>un encabezado estándar y usar algunos de los tipos definidos allí, en particular, int32_tque es exactamente un entero con signo de 32 bits, o uint64_tque es exactamente un entero sin signo de 64 bits, y así sucesivamente. Es posible que desee utilizar tipos comoint_fast16_t por razones de rendimiento.

Lea las respuestas de otros que explican que la aritmética sin signo nunca se derrama (o desborda) en ubicaciones de memoria adyacentes. Cuidado con el comportamiento indefinido en firmado desbordamiento .

Luego, si necesita calcular exactamente números enteros enormes (por ejemplo, si desea calcular factorial de 1000 con todos sus 2568 dígitos en decimal), quiere bigints, también conocidos como números de precisión arbitrarios (o bignums). Los algoritmos para la aritmética bigint eficiente son muy inteligentes, y generalmente requieren el uso de instrucciones de máquina especializadas (por ejemplo, algunos agregan palabras con carry, si su procesador tiene eso). Por lo tanto, recomiendo en ese caso utilizar alguna biblioteca bigint existente como GMPlib

Basile Starynkevitch
fuente