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

Question

Hay dos entradas sin firmar (x e y) que deben restarse. x siempre es mayor que y. Sin embargo, tanto x como y pueden envolverse; por ejemplo, si ambos fueron bytes, después de 0xff viene 0x00. El caso del problema es si x se ajusta, mientras que y no. Ahora x parece ser más pequeño que y. Afortunadamente, x no se ajustará dos veces (solo una vez está garantizado). Suponiendo bytes, x se 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 manera, algo que implica complemento 2s ?, y en este sistema embebido, X e Y son los mayores tipos unsigned int, por lo que añadir 0xff ... es no es posible

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

Answer 1

Suponiendo dos sin firmar enteros:

• Si usted sabe que uno se supone que es "grande" que el otro, solo resta. Funcionará siempre que no se haya envuelto más de una vez (obviamente, si lo ha hecho, no podrá saberlo).
• Si no sabe que una es más grande que la otra, reste y envíe el resultado a una int firmada del mismo ancho. Funcionará siempre que la diferencia entre los dos esté en el rango del int firmado (si no, no podrá contar).

Para aclarar: el escenario descrito por su creador original parece estar confundiendo a la gente, pero es típico de monótonamente crecientes contadores de ancho fijo, como los contadores de garrapatas hardware o 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 usted sabe que de los dos valores xey que usted tiene, x viene después. Si x == 0x02 yy == 0xfe, el cálculo xy (como resultado de 8 bits) arrojará la respuesta correcta de 4, suponiendo que la resta de dos n -bit valores ajusta el módulo 2 ⁿ - que C99 garantías para la resta de valores sin signo. (Nota: el estándar C hace no garantía de este comportamiento para la sustracción de firmado valores.)

Answer 2

Tal vez yo no entiendo, pero ¿qué hay de malo en:

unsigned r = x - y;

Answer 3

La pregunta, como se ha dicho, es confuso. Dijiste que estás restando valores sin firmar. Si x siempre es mayor que y, como dijiste, entonces x - y no puede envolverse o desbordarse. Entonces solo haz x - y (si eso es lo que necesitas) y listo.

Answer 4

Para hacer que todos los demás respondan, si solo resta los dos e interpreta el resultado como no firmado, estará bien.

A menos que tenga un contraejemplo explícito.

Su ejemplo de x = 0x2, y= 0x14 no resultaría en 0x4, que se traduciría en 0xEE, a menos que tenga más restricciones sobre las matemáticas que son no declarado.

Answer 5

Aquí hay un poco más de detalles de por qué 'simplemente funciona' cuando se resta el 'más pequeño' del 'más grande'.

Un par de cosas que entran en esto ...
1. En el hardware, la resta usa la suma: El operando apropiado simplemente se niega antes de ser agregado.
2. En complemento a dos (que utiliza casi todo), un entero es negado invirtiendo todos los bits a continuación, añadir 1.

hardware hace esto de manera más eficiente de lo que parece a partir de 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, permite la figura 2 - 250 con 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 

Niegamos el operando que se resta y luego lo agregamos. Recordemos que para negar invertimos todos los bits a continuación, añadir 1. Después de la inversión de los bits del segundo operando tenemos

0 0 0 0 0 1 0 1 

A continuación, después de añadir 1 tenemos

0 0 0 0 0 1 1 0 

Ahora que realizan la suma ...

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 6

Esta es una manera eficiente de determinar la cantidad de espacio libre en un búfer circular o de controlar el flujo de la ventana deslizante. Use unsigned int s para head y tail - increméntelos y déjelos envolver! La longitud del búfer debe ser una potencia de 2.

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

Answer 7

sólo para poner la respuesta ya correcta en 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 sabe cuál es más pequeña :

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; 
} 

Cuando 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 8

El problema debe plantearse como sigue:

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

Una solución es:

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

sospecho que no hay nada más Prasugrel lo contrario habría algo más eficiente que abs().