menos unario y firmado-a-sin signo de conversión

Question

siempre Es esto técnicamente correcto:

unsigned abs(int n) 
{ 
    if (n >= 0) { 
     return n; 
    } else { 
     return -n; 
    } 
} 

Me parece que aquí si -INT_MIN> INT_MAX, la expresión "-n" podría desbordarse cuando n == INT_MIN , ya que -INT_MIN está fuera de los límites. Pero en mi compilador esto parece funcionar bien ... ¿se trata de un detalle de implementación o un comportamiento confiable?

versión más larga

Un poco de contexto: Estoy escribiendo un C++ envolvente para el tipo entero GMP (mpz_t) y tomando inspiración para el C++ derivador existente GMP (llamado mpz_class). Al manipular adición de mpz_t con enteros con signo existe un código como éste:

static void eval(mpz_ptr z, signed long int l, mpz_srcptr w) 
{ 
    if (l >= 0) 
    mpz_add_ui(z, w, l); 
    else 
    mpz_sub_ui(z, w, -l); 
} 

En otras palabras, si el entero con signo es positivo, añadirla utilizando la rutina de adición sin firmar, si el entero con signo es negativo añadirla utilizando la rutina de la resta sin signo. Ambas rutinas _ _ui toman unsigned long como últimos argumentos. Es la expresión

-l 

¿riesgo de desbordamiento?

Answer 1

Si desea evitar el desbordamiento, primero debe convertir n en unsigned int y luego aplicarle el menos unario.

unsigned abs(int n) { 
    if (n >= 0) 
    return n; 
    return -((unsigned)n); 
} 

En su código original de la negación sucede antes de la conversión de tipos, por lo que el comportamiento no está definido si n < -INT_MAX.

Al negar una expresión sin firmar, nunca habrá desbordamiento. En cambio, el resultado será el módulo 2^x, para el valor apropiado de x.

Answer 2

La mayoría de las computadoras actuales usan una escala de dos números complementarios, lo que significa que la parte negativa es más grande que la positiva, por ejemplo de -128 a 127. Eso significa que si puede representar el número positivo, puede representar la número negativo sin preocupaciones

Answer 3

Sí, se desbordará, a sí mismo.

#include <stdio.h> 
#include <limits.h> 
int main(int argc, char**argv) { 
    int foo = INT_MIN; 
    if (-foo == INT_MIN) printf("overflow\n"); 
    return 0; 
} 

impresiones "desbordamiento"

Sin embargo, este es un comportamiento típico simplemente, no es requerido por la norma. Si desea ir a lo seguro, vea la respuesta aceptada de cómo.

Answer 4

tal vez podría hacer frente a la gama simétrica de los números de complemento a 2:

#include <limits.h> 

unsigned int abs(int n){ 

    unsigned int m; 

    if(n == INT_MIN) 
    m = INT_MAX + 1UL; 
    else if(n < 0) 
    m = -n; 
    else 
    m = n; 

    return m; 
} 

Answer 5

Muy buena pregunta, que expone las diferencias entre C89, C99 y C++. Así que este es un comentario sobre estos Estándares.

En C89, donde n es un int:

(unsigned)n 

no está bien definida para todo n: no hay restricción en la conversión de int con o sin signo, excepto que la representación de un int no negativo firmado es idéntico al de un int sin signo del mismo valor, siempre que ese valor sea representable.

Esto se consideró un defecto, y en C99, lamentablemente hay un intento fallido de restringir la codificación a complemento de dos, complemento o magnitud con el mismo número de bits. Desafortunadamente, el comité C no tenía mucho conocimiento matemático y completamente fallido la especificación: por un lado está mal formado debido a la definición circular y por lo tanto no normativo, y por otro lado, si excusas esta falla, es una sobreconstracción bruta, que, por ejemplo, excluye una representación BCD (utilizada en C en mainframes antiguos de IBM), y también permite que el programador piratee el valor de un entero manipulando bits de la representación (lo cual es muy malo).

C++ se tomó la molestia de proporcionar una mejor especificación, sin embargo, sufre el mismo error de definición circular.

En líneas generales, la representación de un valor v es una matriz de caracteres sin signo con tamaño de elementos (v). Un char sin signo tiene una potencia de dos elementos y debe ser lo suficientemente grande como para garantizar que codifica fielmente cualquier estructura de datos con alias. El número de bits en un carácter no firmado está bien definido como el registro binario del número de valores representables.

El número de bits de cualquier valor sin signo está igualmente bien definido si tiene una potencia de dos números de valores de 0 a 2^n-1, mediante el esquema de codificación de posición canónica.

Desafortunadamente, el comité quería preguntar si había "huecos" en la representación. Por ejemplo, ¿podría tener un número entero de 31 bits en una máquina x86? Digo, lamentablemente, porque esta es una pregunta mal formada, y la respuesta es igualmente incorrecta.

La forma correcta de hacer esta pregunta es preguntar si la representación está completa. No es posible hablar de "los bits de una representación" para enteros con signo porque la especificación no va de la representación a los valores, va en sentido contrario. Esto puede confundir a muchos programadores que piensan incorrectamente que una representación es una asignación de bits subyacentes a algún valor: una representación es una asignación de los valores a los bits.

Una representación está completa si se trata de una superación, es decir, está en todo el rango del espacio de representación. Si la representación está llena, entonces no hay "agujeros", es decir, bits no utilizados. Sin embargo, eso no es todo. Una representación de 255 valores en una matriz de 8 bits no puede estar llena, pero no hay bits que no se utilicen. No hay agujeros

El problema es este: considere un int sin firmar, entonces hay DOS representaciones en bitwise distintas. Existe una matriz bien definida de bits de base de registro 2 determinada a partir de la codificación canónica, y luego está la matriz de bits de la representación física dada por el alias de una matriz de caracteres sin signo. Incluso si esta representación está llena, hay sin correspondencia entre los dos tipos de bits.

Todos sabemos que los "bits de alto orden" de la representación lógica pueden estar en un extremo de la representación física en algunas máquinas y el otro en otras máquinas: se llama endian-ness.Pero, de hecho, no hay ninguna razón para que los bits no se puedan permutar en ningún orden, ¡de hecho no hay ninguna razón para que los bits se alineen en absoluto! Simplemente considere agregar 1 módulo el valor máximo más 1 como representación para ver esto.

Así que ahora el problema es que para enteros con signo hay no representación lógica canónica, sino que hay varios más comunes: complemento de dos, por ejemplo. Sin embargo, como se ve arriba, esto es no relacionado con la representación física. El comité C simplemente no podía entender que la correspondencia entre los valores y la representación física no se puede especificar hablando de los bits. Es se debe especificar por completo hablando de las propiedades de las funciones.

Como esto no se hizo, el estándar C99 contiene galimatías no normativas y, en consecuencia, todas las reglas para el comportamiento de las conversiones de enteros firmadas y no firmadas también son galimatías no normativas.

Por lo tanto, no está claro que

(unsigned)n 

realmente producir el resultado deseado para los valores negativos.

Answer 6

No existe un desbordamiento de enteros sin signo en C. La aritmética para ellos está claramente definida como módulo de cálculo su max + 1, pueden "envolver" pero técnicamente esto no se considera desbordamiento. Entonces, la parte de conversión de tu código está bien, aunque en casos extremos podrías encontrar resultados sorprendentes.

El único punto donde podría haber desbordamiento en su código es el - de un tipo firmado. Hay exactamente un valor para los tipos firmados que pueden no tener una contraparte positiva, el valor mínimo. De hecho, para que se tendría que hacer una comprobación especial, por ejemplo, para int

if (INT_MIN < -INT_MAX && n == INT_MIN) /*do something special*/ 

Answer 7

Esto debe evitar un comportamiento indefinido y trabajar con todas las representaciones de int con signo (complemento a 2, el complemento a 1, signo y magnitud):

unsigned myabs(int v) 
{ 
    return (v >= 0) ? (unsigned)v : (unsigned)-(v+1)+1; 
} 

Los compiladores modernos pueden eliminar el -1+1 redundante y reconocer el modismo para calcular el valor absoluto de un entero con signo.

Esto es lo que produce gcc:

_myabs: 
    movl 4(%esp), %eax 
    cltd 
    xorl %edx, %eax 
    subl %edx, %eax 
    ret