c - que - valor absoluto ejemplos

C tomando con seguridad el valor absoluto del entero

Question

Considere el siguiente programa (C99):

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(void)
{
    printf("Enter int in range %jd .. %jd:/n > ", INTMAX_MIN, INTMAX_MAX);
    intmax_t i;
    if (scanf("%jd", &i) == 1)
        printf("Result: |%jd| = %jd/n", i, imaxabs(i));
}

Ahora como lo entiendo, esto contiene un comportamiento indefinido fácilmente desencadenable, como este:

Enter int in range -9223372036854775808 .. 9223372036854775807:
 > -9223372036854775808
Result: |-9223372036854775808| = -9223372036854775808

Preguntas:

1. ¿Es este comportamiento realmente indefinido, ya que en "se permite que el código active cualquier ruta de código, que cualquier código que traza la fantasía del compilador", cuando el usuario ingresa el número incorrecto? ¿O es algún otro sabor de no completamente definido?

2. ¿Cómo haría un programador pedante para protegerse contra esto, sin hacer suposiciones no garantizadas por el estándar?

(Hay algunas preguntas relacionadas, pero no encontré una que responda a la pregunta 2 anterior, por lo que si sugiere duplicar, asegúrese de que responda a eso).

Answer 1

¿Cómo haría un programador pedante para protegerse contra esto, sin hacer suposiciones no garantizadas por el estándar?

Un método es usar enteros sin signo. El comportamiento de desbordamiento de enteros sin signo está bien definido, ya que es el comportamiento cuando se convierte de un entero con signo a sin signo.

Así que creo que lo siguiente debería ser seguro (resulta que está horriblemente roto en algunos sistemas muy oscuros, ver más adelante en el post una versión mejorada)

uintmax_t j = i;
if (j > (uintmax_t)INTMAX_MAX) {
  j = -j;
}
printf("Result: |%jd| = %ju/n", i, j);

Entonces, ¿cómo funciona esto?

uintmax_t j = i;

Esto convierte el entero con signo en uno sin signo. Si es positivo, el valor permanece igual, si es negativo, el valor aumenta en 2 ⁿ (donde n es el número de bits). Esto lo convierte en un número grande (más grande que INTMAX_MAX)

if (j > (uintmax_t)INTMAX_MAX) {

Si el número original fue positivo (y, por lo tanto, menor o igual que INTMAX_MAX), esto no hace nada. Si el número original era negativo, se ejecuta el interior del bloque if.

  j = -j;

El número es negado. El resultado de una negación es claramente negativo y, por lo tanto, no se puede representar como un entero sin signo. Así se incrementa en 2 ⁿ .

Tan algebraicamente el resultado para negativo me parece

j = - (i + 2 ⁿ ) + 2 ⁿ = -i

Inteligente, pero esta solución hace suposiciones. Esto falla si INTMAX_MAX == UINTMAX_MAX, que está permitido por C Standard.

Hmm, veamos esto (estoy leyendo https://busybox.net/~landley/c99-draft.html que es aproximadamente el último borrador de C99 antes de la estandarización, si algo cambió en la norma final, por favor dígamelo.

Cuando se definen los nombres typedef que difieren solo en la ausencia o presencia de la u inicial, deben denotar los tipos correspondientes firmados y sin firmar como se describe en 6.2.5; una implementación no debe proporcionar un tipo sin proporcionar también su tipo correspondiente.

En 6.2.5 veo

Para cada uno de los tipos de enteros con signo, hay 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 signos) y tiene los mismos requisitos de alineación.

En 6.2.6.2 veo

# 1

Para los tipos de enteros sin signo distintos de los caracteres sin signo, los bits de la representación del objeto se dividirán en dos grupos: bits de valor y bits de relleno (no es necesario que haya ninguno de estos últimos). Si hay N bits de valor, cada bit representará una potencia diferente de 2 entre 1 y 2N-1, de modo que> los objetos de ese tipo podrán representar valores de 0 a 2N-1> usando una representación binaria pura; Esto se conocerá como la representación del valor. Los valores de cualquier bit de relleno no están especificados.39)

# 2

Para los tipos de enteros con signo, los bits de la representación del objeto se dividirán en tres grupos: bits de valor, bits de relleno y el bit de signo. No es necesario que haya bits de relleno; debe haber exactamente un bit de signo. Cada bit que sea un bit de valor tendrá el mismo valor que el mismo bit en la representación del objeto del tipo sin signo correspondiente (si hay bits de valor M en el tipo con signo y N en el tipo sin signo, entonces M <= N). Si el bit de signo es cero, no afectará el valor resultante.

Entonces, sí, parece que tienes razón, mientras que los tipos con y sin signo tienen que ser del mismo tamaño, parece ser válido para que el tipo sin signo tenga un bit de relleno más que el tipo con signo.

Ok, basado en el análisis anterior que revela una falla en mi primer intento, escribí una variante más paranoica. Esto tiene dos cambios desde mi primera versión.

Uso i <0 en lugar de j> (uintmax_t) INTMAX_MAX para verificar si hay números negativos. Esto significa que el algoritmo produce resultados correctos para números mayores o iguales a -INTMAX_MAX incluso cuando INTMAX_MAX == UINTMAX_MAX.

Añado el manejo del caso de error donde INTMAX_MAX == UINTMAX_MAX, INTMAX_MIN == -INTMAX_MAX -1 e i == INTMAX_MIN. Esto resultará en j = 0 dentro de la condición if que podemos probar fácilmente.

Se puede ver en los requisitos del estándar C que INTMAX_MIN no puede ser más pequeño que -INTMAX_MAX -1, ya que solo hay un bit de signo y el número de bits de valor debe ser igual o menor que en el tipo sin signo correspondiente. Simplemente no hay patrones de bits para representar números más pequeños.

uintmax_t j = i;
if (i < 0) {
  j = -j;
  if (j == 0) {
    printf("your platform sucks/n");
    exit(1);
  }
}
printf("Result: |%jd| = %ju/n", i, j);

@plugwash Creo que 2501 es correcto. Por ejemplo, el valor -UINTMAX_MAX se convierte en 1: (-UINTMAX_MAX + (UINTMAX_MAX + 1)), y no es capturado por su if. - Hyde Hace 58 min.

Umm

asumiendo que INTMAX_MAX == UINTMAX_MAX y i = -INTMAX_MAX

uintmax_t j = i;

después de este comando j = -INTMAX_MAX + (UINTMAX_MAX + 1) = 1

si (i <0) {

i es menor que cero, así que ejecutamos los comandos dentro del if

j = -j;

después de este comando j = -1 + (UINTMAX_MAX + 1) = UINTMAX_MAX

que es la respuesta correcta, por lo que no hay necesidad de atraparla en un caso de error.

Answer 2

1. ¿Es este comportamiento realmente indefinido, ya que en "se permite que el código active cualquier ruta de código, que cualquier código que traza la fantasía del compilador", cuando el usuario ingresa el número incorrecto? ¿O es algún otro sabor de no completamente definido?

El comportamiento del programa solo está indefinido, cuando el número incorrecto se ingresa con éxito y se pasa a imaxabs (), que en un sistema de complemento típico de 2 devuelve un resultado como lo observó.

Ese es el comportamiento indefinido en este caso, la implementación también podría terminar el programa con un error de exceso de flujo si la ALU establece indicadores de estado.

El motivo del "comportamiento indefinido" en C es que los escritores del compilador no tienen que protegerse contra el desbordamiento, por lo que los programas pueden ejecutarse de manera más eficiente. Si bien está dentro del estándar C para cada programa C que usa abs () para intentar matar a su primer hijo, simplemente porque lo llama con un valor demasiado -ve, escribir dicho código en el archivo objeto simplemente sería perverso.

El problema real con estos comportamientos indefinidos, es que un compilador de optimización, puede descartar chequeos ingenuos, por lo que código como:

r = (i < 0) ? -i : i;
if (r < 0) {   // This code may be pointless
    // Do overflow recovery
    doRecoveryProcessing();
} else {
    printf("%jd", r);
}

Como un optomiser del compilador puede razonar que los valores negativos son negados, en principio podría determinar que (r <0) siempre es falso, por lo que el intento de atrapar el problema falla.

2. ¿Cómo haría un programador pedante para protegerse contra esto, sin hacer suposiciones no garantizadas por el estándar?

De lejos, la mejor manera es simplemente asegurarse de que el programa funcione en un rango válido, por lo que en este caso la validación de la entrada es suficiente (no permitir INTMAX_MIN). Los programas que imprimen tablas de abs () deben evitar INT * _MIN y así sucesivamente.

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd/n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd/n", i, -(i/10), -(i%10));
    }

Parece escribir el abs (INTMAX_MIN) por fakery, permitiendo que el programa cumpla con lo prometido para el usuario.

Answer 3

En los sistemas de dos complementos, obtener el número absoluto del valor más negativo es, de hecho, un comportamiento indefinido, ya que el valor absoluto estaría fuera de rango. Y no es nada en lo que el compilador pueda ayudarlo, ya que la UB ocurre en tiempo de ejecución.

La única forma de protegerse contra eso es comparar la entrada con el valor más negativo para el tipo ( INTMAX_MIN en el código que muestra).

Answer 4

Entonces, al calcular el valor absoluto de un entero se invoca un comportamiento indefinido en un solo caso. En realidad, aunque se puede evitar el comportamiento indefinido, en un caso es imposible dar el resultado correcto.

Ahora considere la multiplicación de un número entero por 3: Aquí tenemos un problema mucho más serio. ¡Esta operación invoca un comportamiento indefinido en 2 / 3rds de todos los casos! Y para dos tercios de todos los valores int x, encontrar un int con el valor 3x es simplemente imposible. Ese es un problema mucho más serio que el problema de valor absoluto.

Answer 5

Es posible que desee utilizar algunos hacks de bits:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Esto funciona bien cuando INT_MIN < v <= INT_MAX . En el caso donde v == INT_MIN , permanece INT_MIN , sin causar un comportamiento indefinido .

También puede usar la operación bitwise para manejar esto en los sistemas de complemento y de magnitud de signo.

Referencia: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

Answer 6

Si el resultado de imaxabs no se puede representar, puede suceder si se usa el complemento de dos, entonces el comportamiento no está definido .

7.8.2.1 La función imaxabs

2. La función imaxabs calcula el valor absoluto de un entero j. Si el resultado no se puede representar, el comportamiento no está definido. 221)

221) El valor absoluto del número más negativo no puede representarse en el complemento de dos.

El cheque que no hace suposiciones y siempre está definido es:

intmax_t i = ... ;
if( i < -INTMAX_MAX )
{
    //handle error
}

(Esta instrucción if no se puede tomar si se usa el complemento de uno o la representación de magnitud de signo, por lo que el compilador podría dar una advertencia de código inalcanzable. El código en sí todavía está definido y es válido).

Answer 7

de acuerdo con este http://linux.die.net/man/3/imaxabs

Notas

Tratar de tomar el valor absoluto del entero más negativo no está definido.

Para manejar el rango completo, puedes agregar algo como esto a tu código

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd/n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd/n", i, -(i/10), -(i%10));
    }

edición: como abs (INTMAX_MIN) no se puede representar en una máquina de complemento a 2, 2 valores dentro del rango respresentable se concatenan en la salida como una cadena. Probado con gcc, aunque printf requirió% lld como% jd no era un formato compatible.