algorithm - ¿Cómo detecto el desbordamiento mientras multiplico los enteros del complemento de dos 2?
overflow integer-overflow (6)
Quiero multiplicar dos números (el complemento de 2) y detectar si hubo un desbordamiento. ¿Cuál es la forma más sencilla de hacerlo?
Varios idiomas no especifican una comprobación válida para el desbordamiento después de que ocurra, por lo que se requieren pruebas previas.
Con algunos tipos, es posible que no exista un tipo entero más ancho, por lo que una solución general debería limitarse a un solo tipo.
El siguiente ( Ref ) solo requiere comparaciones y límites conocidos para el rango entero. Devuelve 1 si se producirá un desbordamiento de producto, de lo contrario 0 .
int is_undefined_mult1(int a, int b) {
if (a > 0) {
if (b > 0) {
return a > INT_MAX / b; // a positive, b positive
}
return b < INT_MIN / a; // a positive, b not positive
}
if (b > 0) {
return a < INT_MIN / b; // a not positive, b positive
}
return a != 0 && b < INT_MAX / a; // a not positive, b not positive
}
¿Es esta la forma más sencilla? IDK, sin embargo, está completo y maneja todos los casos que conozco.
Quiero multiplicar dos números y detectar si hubo un desbordamiento. ¿Cuál es la forma más sencilla de hacerlo?
Alternativas a la solución de Pavel Shved ...
Si su idioma de elección es el ensamblador, debería poder verificar el indicador de desbordamiento. De lo contrario, podría escribir una rutina de ensamblador personalizada que establezca una variable si se establece el indicador de desbordamiento.
Si esto no es aceptable, puede encontrar el bit de conjunto más significativo de ambos valores (absolutos). Si la suma excede el número de bits en el entero (o sin signo), tendrá un desbordamiento si se multiplican juntos.
Espero que esto ayude.
Compruebe si uno es menor que un valor máximo dividido por el otro. (Todos los valores se toman como absolutos).
La complementariedad de 2 apenas tiene nada que ver con esto, ya que la multiplicación se desborda si x * (2 n - x)> 2 M , que es igual a (x * 2 n - x 2 )> 2 M , o x 2 <(x * 2 n - 2 M ), por lo que tendrá que comparar números desbordantes de todos modos (x 2 puede desbordarse, mientras que el resultado puede no)
En C, aquí hay un código optimizado para madurar que maneja la gama completa de casos de esquinas:
int
would_mul_exceed_int(int a, int b) {
int product_bits;
if (a == 0 || b == 0 || a == 1 || b == 1) return (0); /* always okay */
if (a == INT_MIN || b == INT_MIN) return (1); /* always underflow */
a = ABS(a);
b = ABS(b);
product_bits = significant_bits_uint((unsigned)a);
product_bits += significant_bits_uint((unsigned)b);
if (product_bits == BITS(int)) { /* cases where the more expensive test is required */
return (a > INT_MAX / b); /* remember that IDIV and similar are very slow (dozens - hundreds of cycles) compared to bit shifts, adds */
}
return (product_bits > BITS(int));
}
Ejemplo completo con casos de prueba aquí
El beneficio del enfoque anterior es que no requiere conversión a un tipo más grande, por lo que el enfoque podría funcionar en tipos de enteros más grandes.
Multiplicar dos números de 32 bits da como resultado una respuesta de 64 bits, dos 8s dan un 16, etc. La multiplicación binaria simplemente está cambiando y sumando. por lo tanto, si dijera dos operandos de 32 bits y el bit 17 establecido en el operando A y cualquiera de los bits superiores a 15 o 16 establecidos en el operando b, se desbordará un resultado de 32 bits. el bit 17 desplazado a la izquierda 16 es el bit 33 agregado a 32.
Entonces, nuevamente, la pregunta es cuál es el tamaño de sus entradas y el tamaño de su resultado. Si el resultado es del mismo tamaño, debe encontrar el más significativo. Uno de los dos operandos agrega esas ubicaciones de bits si ese resultado es más grande que sus resultados. espacio que va a desbordar.
EDITAR
Sí, multiplicar dos números de 3 bits resultará en un número de 5 bits o en un número de 6 bits si hay un acarreo en la suma. Del mismo modo, un bit de 2 y 5 bits puede resultar en 6 o 7 bits, etc. Si el motivo de esta pregunta es para ver si tiene espacio en su variable de resultado para una respuesta, esta solución funcionará y es relativamente rápida para la mayoría. Idiomas en la mayoría de los procesadores. Puede ser significativamente más rápido en algunos y significativamente más lento en otros. Es genéricamente rápido (dependiendo de cómo esté implementado, por supuesto) simplemente mirar la cantidad de bits en los operandos. Duplicar el tamaño del operando más grande es una apuesta segura si puede hacerlo dentro de su idioma o procesador. Las divisiones son francamente caras (lentas) y la mayoría de los procesadores no tienen uno mucho menos en una duplicación arbitraria de tamaños de operandos. Por supuesto, lo más rápido es soltar para que el ensamblador realice la multiplicación y observe el bit de desbordamiento (o compare uno de los registros de resultados con cero). Si su procesador no puede hacer la multiplicación en hardware, entonces será lento, no importa lo que haga. Supongo que asm no es la respuesta correcta a esta publicación a pesar de ser el más rápido y el estado de desbordamiento más preciso.
binario hace que la multiplicación sea trivial en comparación con decimal, por ejemplo, toma los números binarios
0b100 * 0b100
Al igual que con las matemáticas decimales en la escuela, puedes (puedes) comenzar con el bit menos significativo en el operando inferior y multiplicarlo por todas las ubicaciones en el operando superior, excepto que con el binario solo hay dos opciones que multiplicas por cero, lo que significa que no tienes que agregar al resultado, o si multiplicas por uno, lo que significa que simplemente cambias y sumas, no es necesaria la multiplicación real como tendrías en el decimal.
000 : 0 * 100 000 : 0 * 100 100 : 1 * 100
Sume las columnas y la respuesta es 0b10000.
Igual que la matemática decimal un 1 en la columna de cientos significa copiar el número superior y agregar dos ceros, funciona igual en cualquier otra base. Entonces 0b100 por 0b110 es 0b1000, uno en la segunda columna sobre, así que copie y agregue un cero + 0b10000 uno en la tercera columna sobre, copie y agregue dos ceros = 0b11000.
Esto lleva a mirar los bits más significativos en ambos números. 0b1xx * 0b1xx garantiza que se agregue 1xxxx a la respuesta, y esa es la ubicación de bits más grande en la adición, no hay otras entradas únicas para la adición final que tengan esa columna rellenada o una columna más significativa. Desde allí solo necesita más bits en caso de que los otros bits que se agregan causen un acarreo.
Lo que sucede con el peor de los casos, todos los tiempos, todos los unos, 0b111 * 0b111
0b00111 + 0b01110 + 0b11100
Esto causa un bit de acarreo en la adición que resulta en 0b110001. 6 bits. un operando de 3 bits por un operando de 3 bits 3 + 3 = 6 6 bits en el peor de los casos.
Por lo tanto, el tamaño de los operandos que utilizan el bit más significativo (no el tamaño de los registros que contienen los valores) determina el requisito de almacenamiento en el peor de los casos.
Bueno, eso es cierto asumiendo operandos positivos. Si consideras que algunos de estos números son negativos, cambia las cosas, pero no mucho.
Menos 4 veces 5, 0b1111 ... 111100 * 0b0000 .... 000101 = -20 o 0b1111..11101100
se necesitan 4 bits para representar un menos 4 y 4 bits para representar un positivo 5 (no olvide su bit de signo). Nuestro resultado requirió 6 bits si se eliminaron todos los signos.
Veamos los casos de esquinas de 4 bits.
-8 * 7 = -56 0b1000 * 0b0111 = 0b1001000 -1 * 7 = -7 = 0b1001 -8 * -8 = 64 = 0b01000000 -1 * -1 = 2 = 0b010 -1 * -8 = 8 = 0b01000 7 * 7 = 49 = 0b0110001
Digamos que contamos números positivos como el más significativo 1 más uno y negativo el más significativo 0 más uno.
-8 * 7 is 4+4=8 bits actual 7 -1 * 7 is 1+4=5 bits, actual 4 bits -8 * -8 is 4+4=8 bits, actual 8 bits -1 * -1 is 1+1=2 bits, actual 3 bits -1 * -8 is 1+4=5 bits, actual 5 bits 7 * 7 is 4+4=8 bits, actual 7 bits.
Entonces, esta regla funciona, con la excepción de -1 * -1, puedes ver que he llamado un bit menos uno, para la cosa más uno encuentra el cero más uno. De todos modos, sostengo que si se tratara de una máquina de 4 bits * 4 bits como se define, tendrías al menos 4 bits de resultados e interpreto la pregunta como si es posible que más de 4 bits necesite almacenar la respuesta de manera segura. Así que esta regla sirve para responder esa pregunta para las matemáticas de complemento a 2s.
Si su pregunta fue determinar con precisión el desbordamiento y luego la velocidad es secundaria, entonces, será realmente muy lenta para algunos sistemas, para cada multiplicación que haga. Si esta es la pregunta que está haciendo, para recuperar parte de la velocidad que necesita, afínelo un poco mejor para el idioma y / o el procesador. Duplique el operando más grande, si puede, y compruebe si hay bits que no sean cero por encima del tamaño del resultado, o utilice una división y compare. Si no puede duplicar los tamaños del operando, divida y compare. Compruebe si hay cero antes de la división.
En realidad, su pregunta no especifica de qué tamaño de desbordamiento está hablando. El antiguo 8086 16 bit por 16 bit da un resultado de 32 bit (hardware), que nunca puede desbordarse. ¿Qué pasa con algunas de las ARM que tienen un resultado de 32 bits multiplicado, 32 bits, 32 bits, fácil de desbordar? ¿Cuál es el tamaño de sus operandos para esta pregunta, son del mismo tamaño o duplican el tamaño de entrada? ¿Está dispuesto a realizar multiplicaciones que el hardware no puede hacer (sin desbordarse)? ¿Está escribiendo una biblioteca de compiladores y tratando de determinar si puede alimentar los operandos al hardware para la velocidad o si tiene que realizar los cálculos matemáticos sin multiplicar el hardware? ¿Cuál es el tipo de cosa que obtienes si inviertes los operandos, la biblioteca del compilador intentará volver a lanzar los operandos antes de hacer la multiplicación, dependiendo del compilador y su biblioteca, por supuesto? Y utilizará el conteo del bit truco determinado para usar el hardware multiplicado o uno de software.
Mi objetivo aquí era mostrar cómo funciona la multiplicación binaria en una forma digerible para que pueda ver cuánto almacenamiento máximo necesita al encontrar la ubicación de un solo bit en cada operando. Ahora, lo rápido que puede encontrar ese bit en cada operando es el truco. Si buscaba requisitos mínimos de almacenamiento, no es el máximo, es una historia diferente, ya que cada uno de los bits significativos en ambos operandos, no solo un bit por operando, debe hacer la multiplicación para determinar el almacenamiento mínimo. Si no te importa el almacenamiento máximo o mínimo, solo tienes que hacer la multiplicación y buscar ceros que no superen tu límite de desbordamiento definido o usar una división si tienes el tiempo o el hardware.
Sus etiquetas implican que no está interesado en el punto flotante, el punto flotante es una bestia completamente diferente, no puede aplicar ninguna de estas reglas de punto fijo al punto flotante, NO funcionan.
Si su número no pertenece al tipo de datos integral más grande, entonces puede simplemente juntarlos, multiplicarlos y compararlos con el máximo del tipo original del número. Por ejemplo, en Java, al multiplicar dos int , puede convertirlos en long y comparar el resultado con Integer.MAX_VALUE o Integer.MIN_VALUE (dependiendo de la combinación de signos), antes de convertir el resultado en int .
Si el tipo ya es el más grande, verifique si uno es menor que el valor máximo dividido por el otro. ¡Pero no tome el valor absoluto! En su lugar, necesita una lógica de comparación por separado para cada una de las combinaciones de signos neg neg, pos pos y pos neg (la posición negativa puede obviamente reducirse a pos neg, y la posición pos puede reducirse a neg * neg). Primera prueba para 0 argumentos para permitir divisiones seguras.
Para el código real, vea la fuente Java de la clase MathUtils de commons-math 2, o ArithmeticUtils de commons-math 3 . Busque public static long mulAndCheck(long a, long b) . El caso de los positivos ayb es
// check for positive overflow with positive a, positive b
if (a <= Long.MAX_VALUE / b) {
ret = a * b;
} else {
throw new ArithmeticException(msg);
}