¿Cómo detecto el desbordamiento al multiplicar dos enteros complementarios de 2?

Question

Quiero multiplicar dos números y detectar si hubo un desbordamiento. ¿Cuál es la forma más simple de hacer eso?

Answer 1

Compruebe si uno es menor que un valor máximo dividido por el otro. (Todos los valores se toman como absolutos).

complementness de 2 casi no tiene nada que ver con esto, ya que la multiplicación se desborda si x * (2 ⁿ - x)> 2 ^M, que es igual a (x * 2 ⁿ - x)> 2 ^M, ox < (x * 2 ⁿ - 2 ^M), por lo que tendrá que comparar los números de todas formas desbordantes (x 2 puede desbordar, mientras que resultado puede no)

Answer 2

Alternativas a la solución de Pavel Shved ...

Si el idioma de su elección es ensamblador, entonces usted debería ser capaz de comprobar el indicador de desbordamiento. De lo contrario, podría escribir una rutina de ensamblador personalizada que establezca una variable si se estableció el indicador de desbordamiento.

Si esto no es aceptable, puede encontrar el bit establecido más significativo de ambos valores (absolutos). Si la suma excede el número de bits en el entero (o sin signo), entonces tendrá un desbordamiento si se multiplican juntos.

Espero que esto ayude.

Answer 3

Si su número no es del tipo de datos integral más grande, entonces puede simplemente crearlos, multiplicarlos y compararlos con el máximo del tipo original del número. P.ej. en Java, al multiplicar dos int, puede convertirlos a long y comparar el resultado a Integer.MAX_VALUE o Integer.MIN_VALUE (según la combinación de signos), antes de arrojar el resultado hasta int.

Si el tipo ya es el más grande, entonces verifique si uno es menor que el valor máximo dividido por el otro. ¡Pero no tomes el valor absoluto! En su lugar lo que necesita lógica de comparación por separado para cada una de las combinaciones de signos neg neg , pos POS y neg (NEG POS pueden, obviamente, ser reducidos a pos neg, y pos pos podrían reducirse a neg neg *). Primero prueba 0 argumentos para permitir divisiones seguras.

Para obtener el código actual, consulte la fuente Java de MathUtils clase de commons-math 2 o ArithmeticUtils de commons-math 3. Busque public static long mulAndCheck(long a, long b). El caso de la positivo a y b es

// check for positive overflow with positive a, positive b 
if (a <= Long.MAX_VALUE/b) { 
    ret = a * b; 
} else { 
    throw new ArithmeticException(msg); 
} 

Answer 4

multiplicar dos 32 números de bits da como resultado una respuesta de 64 bits, dos 8s dan un 16, etc. multiplicación binaria es simplemente desplazando y la adición. así que si tuviera dos operandos de 32 bits y el bit 17 configurado en el operando A y cualquiera de los bits superiores a 15 o 16 establecidos en el operando b, desbordará un resultado de 32 bits. el bit 17 se desplazó a la izquierda 16 y el bit 33 se agregó a un 32.

Así que 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, entonces tiene que encontrar el más significativo 1 de ambos operandos agregar esas ubicaciones de bits si ese resultado es más grande que su espacio de resultados se desbordará.

EDITAR

Sí multiplicar dos números de 3 bits den lugar a un número de 5 bits o número de 6 bits si hay un acarreo en el complemento. Del mismo modo, un bit de 2 y 5 bits puede dar como resultado 6 o 7 bits, etc. Si el motivo de esta pregunta es ver si hay espacio en la variable de resultado para una respuesta, entonces 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 se implemente, por supuesto) simplemente mirar el número de bits en los operandos. Duplicar el tamaño del operando más grande es una apuesta segura si puede hacerlo dentro de su lenguaje o procesador. Las divisiones son francamente caras (lentas) y la mayoría de los procesadores no tienen una mucho menos en una duplicación arbitraria de los tamaños de operandos. El más rápido, por supuesto, es bajar al ensamblador para multiplicar y mirar el bit de desbordamiento (o comparar uno de los registros de resultados con cero). Si su procesador no puede multiplicar en hardware, será lento sin importar lo que haga. Supongo que asm no es la respuesta correcta para 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 trivial comparado con decimales, por ejemplo, tomar los números binarios

 
0b100 * 
0b100 

Al igual que las matemáticas decimal en la escuela que (puede) comenzar con el bit menos significativo en el operando inferior y se multiplica contra todos 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 multiplicas por uno, lo que significa que simplemente cambias y agregas, no es necesaria una multiplicación real como lo harías tener en decimal.

 
    000 : 0 * 100 
000 : 0 * 100 
100 : 1 * 100 

Sume las columnas y la respuesta es 0b10000

Igual que las matemáticas decimal un 1 en los cientos columna significa copiar el número de arriba y añadir dos ceros, que funciona de la misma en cualquier otra base, así . Así que 0b100 veces 0b110 es 0b1000, uno en la segunda columna, así que copie y agregue un cero + 0b10000 a uno en la tercera columna, así que copie y agregue dos ceros = 0b11000.

Esto lleva a buscar los bits más significativos en ambos números. 0b1xx * 0b1xx garantiza que se agrega un 1xxxx a la respuesta, y esa es la ubicación de bit más grande en el complemento, ninguna otra entrada individual al agregado final tiene esa columna poblada o una columna más importante poblada. A partir de ahí, solo necesitará más bits en caso de que los otros bits que se sumen generen un acarreo.

¿Qué ocurre con el peor de los casos todos unos tiempos todos unos, 0b111 * 0b111

 
0b00111 + 
0b01110 + 
0b11100 

Esto provoca un bit de acarreo en la adición 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.

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 peor requisito de almacenamiento de casos.

Bueno, eso es cierto asumiendo operandos positivos. Si considera que algunos de estos números son negativos, cambia las cosas pero no mucho.

Minus 4 veces 5, 0b1111 ... 111100 * 0b0000 .... 000 101 = -20 o 0b1111..11101100

toma 4 bits para representar un signo menos 4 y 4 bits para representar un positivo 5 (no olvide su bit de signo). Nuestro resultado requirió 6 bits si eliminó todos los bits de signo.

deja mirada en los casos de esquina 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 los más significativos 1 más uno y negativa los más significativos 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. 

Así que esta regla funciona, con la excepción de -1 * -1, se puede ver que llamé a un menos uno un bit, para el más una cosa encontrar el más uno igual a cero. De todos modos, defiendo que si se tratara de una máquina de 4 bits * 4 bits como se define, tendrías al menos 4 bits de resultado e interpreto la pregunta de cómo puedo almacenar más de 4 bits de forma segura la respuesta. Entonces, esta regla sirve para responder esa pregunta para el complemento matemático 2.

Si su pregunta era determinar con precisión el desbordamiento y luego la velocidad es secundaria, entonces, va a ser realmente muy lento para algunos sistemas, para cada multiplicación que haga. Si esta es la pregunta que está haciendo, para recuperar parte de la velocidad, debe ajustarla un poco mejor para el idioma y/o procesador. Duplique el operando más grande, si puede, y verifique que no haya bits por encima del tamaño del resultado, o use una división y compare. Si no puede doblar el tamaño de los operandos, divida y compare. Verifica cero antes de la división.

En realidad, su pregunta no especifica de qué tamaño de desbordamiento está hablando tampoco. El buen viejo 8086 16 bit por 16 bit da un resultado de 32 bit (hardware), nunca puede desbordarse. ¿Qué pasa con algunos de los ARM que tienen un resultado multiplicado, 32 bit por 32 bit, 32 bit, fácil de desbordar? ¿Cuál es el tamaño de sus operandos para esta pregunta, son del mismo tamaño o son el doble del tamaño de entrada? ¿Estás dispuesto a realizar multiplicaciones que el hardware no puede hacer (sin desbordamiento)? ¿Está escribiendo una biblioteca de compilación y tratando de determinar si puede alimentar los operandos al hardware para la velocidad o si tiene que realizar las operaciones matemáticas sin multiplicar hardware? Cuál es el tipo de cosa que obtienes si creas los operandos, la biblioteca del compilador intentará volver a echar los operandos antes de multiplicar, dependiendo del compilador y su biblioteca, por supuesto. Y usará el recuento del truco de bits para usar el multiplicador de hardware o uno de software.

Mi objetivo aquí fue mostrar cómo funciona la multiplicación binaria en una forma digerible para que pueda ver la cantidad máxima de almacenamiento que necesita al encontrar la ubicación de un solo bit en cada operando. Ahora, qué tan rápido puede encontrar ese bit en cada operando es el truco. Si buscaba requisitos mínimos de almacenamiento, no el máximo, esa es una historia diferente porque implica cada uno de los bits significativos en ambos operandos, no solo un bit por operando, debe multiplicar para determinar el almacenamiento mínimo. Si no le preocupa el almacenamiento máximo o mínimo, simplemente tiene que multiplicar y buscar no ceros por encima de su límite de desbordamiento definido o utilizar una división si tiene el tiempo o el hardware.

Tus etiquetas implican que no estás interesado en el punto flotante, el punto flotante es una bestia completamente diferente, no puedes aplicar ninguna de estas reglas de punto fijo al punto flotante, NO FUNCIONAN.

Answer 5

En C, aquí hay un código con madurez optimizado que se encarga de toda la gama de casos de esquina:

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

Full example with test cases here

La ventaja de este método es que no requiere la fundición hasta una más grande tipo, por lo que el enfoque podría funcionar en tipos enteros más grandes.