Come si rileva l'overflow mentre si moltiplicano i due interi del complemento a 2?

Question

Voglio moltiplicare due numeri e rilevare se c'è stato un overflow. Qual è il modo più semplice per farlo?

Answer 1

Verificare se uno è inferiore al valore massimo diviso dall'altro. (Tutti i valori sono considerati assoluti).

complementness 2 di poco ha a che fare con essa, dal momento che la moltiplicazione trabocca se x * (2 ⁿ - x)> 2 ^M, che è uguale a (x * 2 ⁿ - x)> 2 ^M, o x < (x * 2 ⁿ-2 ^M), quindi dovrete confrontare in ogni caso i numeri traboccanti (x 2 può traboccare, mentre il risultato non possono).

Answer 2

Alternative alla soluzione di Pavel Shved ...

Se la lingua di scelta è assemblatore, allora si dovrebbe essere in grado di controllare il flag di overflow. In caso contrario, è possibile scrivere una routine assembler personalizzata che imposta una variabile se è stato impostato il flag di overflow.

Se ciò non è accettabile, è possibile trovare il bit impostato più significativo di entrambi i valori (assoluti). Se la somma supera il numero di bit nel numero intero (o non firmato), si avrà un overflow se vengono moltiplicati insieme.

Spero che questo aiuti.

Answer 3

Se il tuo numero non è il più grande tipo di dati integrale, potresti semplicemente lanciarlo, moltiplicarlo e confrontarlo con il massimo del tipo originale del numero. Per esempio. in Java, quando si moltiplicano due long, è possibile convertirli in long e confrontare il risultato con Integer.MAX_VALUE o Integer.MIN_VALUE (a seconda della combinazione di segno), prima di trasmettere il risultato fino a int.

Se il tipo è già il più grande, controllare se uno è inferiore al valore massimo diviso dall'altro. Ma non prendere il valore assoluto! Invece è necessaria una logica di confronto separata per ciascuna delle combinazioni di segni neg neg, pos pos e pos neg (neg pos può ovviamente essere ridotto a pos neg e pos pos potrebbe essere ridotto a neg * neg). Primo test per 0 argomenti per consentire divisioni sicure.

Per il codice effettivo, vedere la sorgente Java della classe MathUtils di commons-math 2 o ArithmeticUtils di commons-math 3. Cerca public static long mulAndCheck(long a, long b). Il caso per positivo a e b è

// 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

Moltiplicando due numeri a 32 bit determina una risposta 64 bit, due 8s danno 16, ecc moltiplicazione binaria viene semplicemente spostando e aggiungendo. quindi se aveste detto due operandi a 32 bit e il bit 17 impostati nell'operando A e uno qualsiasi dei bit superiori a 15 o 16 impostati nell'operando b, si verificherà un overflow di un risultato a 32 bit. il bit 17 spostato a sinistra 16 è il bit 33 aggiunto a un 32.

Quindi la domanda è di nuovo quale sia la dimensione dei tuoi input e la dimensione del tuo risultato, se il risultato è la stessa dimensione allora devi trovare il più significativo 1 di entrambi gli operandi aggiungere quelle posizioni di bit se tale risultato è più grande del tuo spazio dei risultati ti eccederai.

EDIT

Sì moltiplicare due numeri di bit 3 si tradurrà in un numero 5 bit o il numero 6 bit se c'è un riporto del componente aggiuntivo. Allo stesso modo un 2 bit e 5 bit possono risultare in 6 o 7 bit, ecc. Se il motivo di questa domanda è di vedere se nella tua variabile risultato c'è spazio per una risposta, allora questa soluzione funzionerà e sarà relativamente veloce per la maggior parte lingue sulla maggior parte dei processori. Può essere significativamente più veloce su alcuni e notevolmente più lento sugli altri. È genericamente veloce (a seconda di come viene implementato, ovviamente) per osservare il numero di bit negli operandi. Raddoppiare la dimensione dell'operando più grande è una scommessa sicura se puoi farlo nella tua lingua o processore. Le divisioni sono decisamente costose (lente) e la maggior parte dei processori non ne ha una molto meno in un raddoppio arbitrario delle dimensioni degli operandi. Il più veloce, naturalmente, è quello di rilasciare all'assemblatore la moltiplicazione e guardare il bit di overflow (o confrontare uno dei registri dei risultati con zero). Se il tuo processore non riesce a moltiplicare in hardware, allora sarà lento, qualunque cosa tu faccia. Immagino che asm non sia la risposta giusta a questo post, nonostante sia di gran lunga la più veloce e abbia lo stato di overflow più accurato.

binario rende la moltiplicazione banale rispetto al decimale, ad esempio, prendere i numeri binari

 
0b100 * 
0b100 

Proprio come la matematica decimale a scuola si (possibile) iniziare con il bit meno significativo sulla operando inferiore e moltiplicarlo contro tutti le posizioni nell'operando superiore, tranne che con il binario ci sono solo due scelte che moltiplica per zero, ovvero che non devi aggiungere al risultato, o moltiplichi per una che significa che devi solo spostare e aggiungere, nessuna moltiplicazione effettiva è necessaria come faresti avere in decimale.

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

Aggiungere le colonne e la risposta è 0b10000

Idem come la matematica decimale una 1 nelle centinaia di colonna significa copiare il numero in alto e aggiungere due zeri, funziona lo stesso in qualsiasi altra base come pure . Quindi 0b100 volte 0b110 è 0b1000, uno nella seconda colonna in modo da copiare e aggiungere uno zero + 0b10000 uno nella terza colonna in modo da copiare e aggiungere due zeri = 0b11000.

Questo porta a considerare i bit più significativi in ​​entrambi i numeri. 0b1xx * 0b1xx garantisce che alla risposta sia aggiunto 1xxxx, e che è la più grande posizione di bit nell'aggiunta, nessun altro singolo input all'aggiunta finale ha la colonna popolata o una colonna più significativa popolata. Da lì è necessario solo più bit nel caso in cui gli altri bit che vengono aggiunti causano un carry.

che avviene con il caso peggiore tutte quelle volte tutti quelli, 0b111 * 0b111

 
0b00111 + 
0b01110 + 
0b11100 

Questo provoca un bit di riporto in aggiunta conseguente 0b110001. 6 bit. un operando a 3 bit per un operando a 3 bit 3 + 3 = 6 6 bit caso peggiore.

Quindi la dimensione degli operandi che utilizzano il bit più significativo (non la dimensione dei registri che contengono i valori) determina il peggiore requisito di archiviazione.

Bene, questo è vero assumendo operandi positivi. Se consideri alcuni di questi numeri negativi, cambia le cose ma non di molto.

Minus 4 volte 5, 0b1111 ... 111100 * 0b0000 .... 000101 = -20 o 0b1111..11101100

occorrono 4 bit per rappresentare un meno 4 e 4 bit per rappresentare un positivo 5 (non dimenticare il tuo segno bit). Il nostro risultato richiedeva 6 bit se toglievi tutti i bit del segno.

consente di guardare i casi d'angolo 4 bit

 
-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 

Diciamo contiamo numeri positivi come il più significativo 1 più uno e negativo il più significativo 0 più 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. 

Quindi questa regola funziona, con l'eccezione di -1 * -1, si può vedere che ho chiamato un meno uno un bit, per la più una cosa trovare lo zero più uno. Ad ogni modo, io sostengo che se questo fosse una macchina * 4 bit a 4 bit come definito, si dovrebbe 4 bit di risultato almeno e interpretare la questione di come possono più di 4 bit fare ho bisogno di memorizzare in modo sicuro la risposta. Quindi questa regola serve a rispondere a questa domanda per la matematica del complemento 2s.

Se la tua domanda è stato quello di determinare con precisione di troppo pieno e quindi la velocità è secondario, quindi, ben si sta per essere davvero molto lento per alcuni sistemi, per ogni moltiplicare che fate. Se questa è la domanda si sta chiedendo, per avere un po 'di velocità di nuovo è necessario sintonizzare un po' meglio per la lingua e/o del processore. Raddoppia l'operando più grande, se puoi, e controlla i bit diversi da zero al di sopra della dimensione del risultato, oppure usa una divisione e confronta. Se non riesci a raddoppiare le dimensioni dell'operando, dividi e confronta. Controlla zero prima della divisione.

In realtà la tua domanda doesnt specificare quali dimensioni di troppo pieno si sta parlando sia. Il buon vecchio 8086 16 bit 16 bit dà un risultato a 32 bit (hardware), non può mai traboccare. Che dire di alcuni ARM che hanno un risultato moltiplicato, 32 bit a 32 bit, a 32 bit, facilmente overflow. Qual è la dimensione dei tuoi operandi per questa domanda, hanno le stesse dimensioni o raddoppiano la dimensione dell'input? Sei disposto a eseguire multipli che l'hardware non può fare (senza traboccare)? Stai scrivendo una libreria di compilatore e cercando di determinare se è possibile alimentare gli operandi per l'hardware per la velocità o se è necessario eseguire la matematica senza moltiplicare hardware. Qual è il genere di cosa che si ottiene se si lanci le operandi, la biblioteca compilatore cercherà di gettare le operandi indietro prima di fare la moltiplicazione, a seconda del compilatore e la sua biblioteca, naturalmente. E userà il conteggio che il trucco del bit determina per usare l'hardware moltiplicato o uno software.

Il mio obiettivo era mostrare come funziona il multiplo binario in una forma digeribile in modo da poter vedere quanta memoria massima è necessaria trovando la posizione di un singolo bit in ciascun operando. Ora la velocità con cui riesci a trovare quel bit in ogni operando è il trucco. Se stai cercando requisiti minimi di memoria non al massimo, è una storia diversa perché coinvolge ogni singolo bit significativo in entrambi gli operandi, non solo un bit per operando, devi fare il multiplo per determinare la memoria minima. Se non ti interessa l'archiviazione massima o minima devi semplicemente moltiplicare il numero e cercare zeri al di sopra del tuo limite di overflow definito o utilizzare una divisione se hai tempo o hardware.

I tag implicano che non sei interessato a virgola mobile, il virgola mobile è una bestia completamente diversa, non puoi applicare nessuna di queste regole a virgola fissa a virgola mobile, NON funzionano.

Answer 5

In C, ecco qualche codice maturo ottimizzato che gestisce l'intera gamma di casi d'angolo:

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

Il vantaggio del metodo di cui sopra è che non richiede la fusione fino ad una più grande digita, quindi l'approccio potrebbe funzionare su tipi interi più grandi.