Pregunta ¿Es el comportamiento definido de la resta entera sin signo?


Me encontré con el código de alguien que parece creer que hay un problema al sustraer un entero sin signo de otro entero del mismo tipo cuando el resultado sería negativo. Entonces, ese código sería incorrecto incluso si funciona en la mayoría de las arquitecturas.

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

Esta es la única cita vagamente relevante del estándar C que pude encontrar.

Una computación que involucre operandos sin firmar nunca puede sobrecargarse, porque una   resultado que no puede ser representado por el entero sin signo resultante   tipo es módulo reducido el número que es uno mayor que el más grande   valor que puede ser representado por el tipo resultante.

Supongo que se podría tomar esa cita para indicar que cuando el operando correcto es más grande, la operación se ajusta para que tenga sentido en el contexto de los números truncados en el módulo.

es decir

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

en lugar de utilizar la semántica firmada dependiente de la implementación:

0x0000 - 0x0001 == (sin signo) (0 + -1) == (0xFFFF pero también 0xFFFE o 0x8001)

¿Cuál o qué interpretación es la correcta? ¿Está definido en absoluto?


76
2017-08-28 13:59


origen


Respuestas:


El resultado de una resta que genera un número negativo en un tipo sin signo está bien definido:

  1. [...] Un cálculo que involucra operandos sin firmar nunca puede desbordarse,   porque un resultado que no puede ser representado por el tipo de entero sin signo resultante es   módulo reducido el número que es uno mayor que el valor más grande que puede ser   representado por el tipo resultante.   (ISO / IEC 9899: 1999 (E) §6.2.5 / 9)

Como puedes ver, (unsigned)0 - (unsigned)1 es igual a -1 módulo UINT_MAX + 1, o en otras palabras, UINT_MAX.

Tenga en cuenta que, si bien dice "Un cómputo que involucre operandos sin firmar nunca puede desbordarse", lo que podría llevarlo a creer que se aplica solo por exceder el límite superior, esto se presenta como un motivación para la parte vinculante real de la oración: "un resultado que no puede ser representado por el tipo de entero sin signo resultante es módulo reducido el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante. "Esta frase no está restringida al desbordamiento del límite superior del tipo, y se aplica igualmente a valores demasiado bajos para ser representados.


84
2017-08-28 14:06



Cuando trabajas con no firmado tipos, aritmética modular (también conocido como "envolver alrededor" comportamiento) está teniendo lugar. Para entender esto aritmética modular, solo eche un vistazo a estos relojes:

enter image description here 

9 + 4 = 1 (13 mod 12), por lo que a la otra dirección es: 1 - 4 = 9 (-3 mod 12) El mismo principio se aplica al trabajar con tipos sin firmar. Si el tipo de resultado es unsigned, entonces tiene lugar la aritmética modular.


Ahora mira las siguientes operaciones almacenando el resultado como una unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Cuando quiera asegurarse de que el resultado sea signed, luego lo almacenó en signedvariable o emitirlo a signed. Cuando desee obtener la diferencia entre los números y asegurarse de que no se aplicará la aritmética modular, debe considerar usar abs() función definida en stdlib.h:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Tenga mucho cuidado, especialmente al escribir las condiciones, porque:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

pero

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...

96
2018-02-22 17:56



Bueno, la primera interpretación es correcta. Sin embargo, su razonamiento sobre la "semántica firmada" en este contexto es incorrecto.

De nuevo, tu primera interpretación es correcta. La aritmética sin signo sigue las reglas de la aritmética de módulo, lo que significa que 0x0000 - 0x0001 evalúa a 0xFFFF para tipos sin firmar de 32 bits.

Sin embargo, la segunda interpretación (la basada en "semántica firmada") también es necesaria para producir el mismo resultado. Es decir. incluso si evalúas 0 - 1 en el dominio de tipo firmado y obtener -1 como el resultado intermedio, esto -1 todavía se requiere para producir 0xFFFF cuando más tarde se convierte a tipo sin firmar. Incluso si alguna plataforma utiliza una representación exótica para enteros con signo (complemento de 1, magnitud con signo), esta plataforma aún debe aplicar reglas de aritmética de módulo al convertir valores enteros con signo a los sin signo.

Por ejemplo, esta evaluación

signed int a = 0, b = 1;
unsigned int c = a - b;

todavía está garantizado para producir UINT_MAX en c, incluso si la plataforma está utilizando una representación exótica para enteros con signo.


3
2018-02-22 18:22



Con números sin firmar de tipo unsigned int o más grande, en ausencia de conversiones de tipo, a-b se define como la obtención del número sin signo que, cuando se agrega a b, rendirá a. La conversión de un número negativo a sin signo se define como la obtención del número que, cuando se agrega al número original de signo invertido, arrojará cero (por lo que convertir -5 en no firmado arrojará un valor que, cuando se agrega a 5, arrojará cero) .

Tenga en cuenta que los números sin signo más pequeños que unsigned int puede ser promovido a tipo int antes de la resta, el comportamiento de a-b dependerá del tamaño de int.


2
2018-01-09 17:22