Cómo restar dos entradas sin firmar con envolvente o desbordamiento

overflow int

Question

Hay dos entradas sin firmar (x e y) que deben ser restadas. x es siempre más grande que y. Sin embargo, tanto x como y pueden envolver alrededor; por ejemplo, si ambos eran bytes, después de 0xff viene 0x00. El caso problemático es si x se ajusta, mientras que y no lo hace. Ahora x parece ser más pequeño que y. Afortunadamente, x no se ajustará dos veces (solo una vez está garantizada). Suponiendo bytes, x ha envuelto y ahora es 0x2, mientras que y no tiene y es 0xFE. La respuesta correcta de x - y se supone que es 0x4.

Tal vez,

( x > y) ? (x-y) : (x+0xff-y);

Pero creo que hay otra forma, ¿algo relacionado con el cumplido de 2s ?, y en este sistema integrado, xey son los tipos int más grandes sin signo, por lo que agregar 0xff ... no es posible

¿Cuál es la mejor manera de escribir la declaración (el idioma de destino es C)?

Answer 1

Aquí hay un poco más de detalles de por qué "simplemente funciona" cuando restas "más pequeño" de "más grande".

Un par de cosas entrando en esto ...
1. En hardware, la resta usa la suma: el operando apropiado simplemente se niega antes de ser agregado.
2. En el complemento a dos (que utiliza casi todo), un entero se niega invirtiendo todos los bits y luego agrega 1.

El hardware hace esto más eficientemente de lo que parece en la descripción anterior, pero ese es el algoritmo básico para la resta (incluso cuando los valores no están firmados).

Por lo tanto, vamos a la figura 2 - 250 usando enteros sin signo de 8 bits. En binario tenemos

  0 0 0 0 0 0 1 0  
- 1 1 1 1 1 0 1 0

Negamos el operando que se está restando y luego sumamos. Recuerde que para negar invirtimos todos los bits y luego sumamos 1. Después de invertir los bits del segundo operando tenemos

0 0 0 0 0 1 0 1  

Luego, después de agregar 1 tenemos

0 0 0 0 0 1 1 0  

Ahora realizamos la adición ...

  0 0 0 0 0 0 1 0   
+ 0 0 0 0 0 1 1 0

= 0 0 0 0 1 0 0 0 = 8, which is the result we wanted from 2 - 250

Answer 2

El problema debe plantearse como sigue:

Supongamos que la posición (ángulo) de dos punteros a y b de un reloj viene dada por uint8_t. Toda la circunferencia se divide en los 256 valores de un uint8_t. ¿Cómo se puede calcular de manera eficiente la distancia más pequeña entre los dos punteros?

Una solución es:

uint8_t smaller_distance = abs( (int8_t)( a - b ) );

Sospecho que no hay nada más eficiente, de lo contrario habría algo más eficiente que abs ().

Answer 3

Esta es una forma eficiente de determinar la cantidad de espacio libre en un búfer circular o hacer un control de flujo de ventana deslizante. Use unsigned int para head y tail : ¡incrementelos y déjelos envolver! La longitud del búfer tiene que ser una potencia de 2.

free = ((head - tail) & size_mask) , donde size_mask es 2 ^ n-1 el tamaño del búfer o la ventana.

Answer 4

La pregunta, como se ha dicho, es confusa. Dijiste que estás restando valores sin firmar. Si x siempre es más grande que y , como dijiste, entonces x - y no es posible envolver o desbordar. Así que solo haces x - y (si eso es lo que necesitas) y eso es todo.

Answer 5

Para repetir a todos los demás que responden, si solo restas los dos e interpretas el resultado como no firmado, estarás bien.

A menos que tengas un contraejemplo explícito.

Su ejemplo de x = 0x2 , y= 0x14 no daría como resultado 0x4 , daría como resultado 0xEE , a menos que tenga más restricciones en las matemáticas que no están expresadas.

Answer 6

Solo para poner la respuesta ya correcta en el código:

Si sabe que x es el valor más pequeño, el siguiente cálculo simplemente funciona:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    uint8_t res = y - x;
    printf("Expect 20: %d/n", res); // res is 20

    return 0;
}

Si no sabes cuál es más pequeño:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    int8_t res1 = (int8_t)x - y;
    int8_t res2 = (int8_t)y - x;
    printf("Expect -20 and 20: %d and %d/n", res1, res2);

    return 0;
}

Donde la diferencia debe estar dentro del rango de uint8_t en este caso.

El experimento del código me ayudó a entender mejor la solución.

Answer 7

Suponiendo dos enteros sin signo :

• Si sabe que se supone que uno es "más grande" que el otro, simplemente reste. Funcionará siempre que no se haya envuelto más de una vez (obviamente, si lo ha hecho, no podrá decirlo).
• Si no sabe que uno es más grande que el otro, reste y convierta el resultado a un int firmado del mismo ancho. Funcionará siempre que la diferencia entre los dos esté en el rango del int firmado (de lo contrario, no podrá decirlo).

Para aclarar: el escenario descrito por el póster original parece confundir a la gente, pero es típico de los contadores de ancho fijo que aumentan monótonamente, como los contadores de tic tac de hardware o los números de secuencia en los protocolos. El contador va (por ejemplo, para 8 bits) 0xfc, 0xfd, 0xfe, 0xff, 0x00, 0x01, 0x02, 0x03, etc., y sabe que de los dos valores x e y que tiene, x viene más tarde. Si x == 0x02 y y == 0xfe, el cálculo xy (como un resultado de 8 bits) dará la respuesta correcta de 4, suponiendo que la resta de dos valores de ⁿ bits encierra el módulo 2 ⁿ , lo que C99 garantiza para la resta de Valores sin firmar. (Nota: el estándar C no garantiza este comportamiento para la resta de valores firmados ).

Answer 8

Tal vez no entiendo, pero lo que está mal con:

unsigned r = x - y;