mercoledì 1 agosto 2018

Moltiplicazioni binarie solo con addizioni e bit shift

Una delle cose che mi ha piu' spiazzato nell'imparare l'assembler per C64 e' l'assenza nel set di istruzione del 6502/6510 di un opcode per moltiplicare. anche i soli interi

La soluzione per fare una moltiplicazione con soli addizioni e bit shift e' in realta' molto semplice usando la matematica binaria

Si parte da un esempio semplice 9 (1001b) x 8 (1000b). Se si usa la regola della moltiplicazione in colonna che si impara alle elementari

            1001x 
       1000=
      ------
       0000
      0000
     0000
    1001
    ------------
    1001000   (72d)

Come si vede quando si ha un bit zero e' inutile effettuare la moltiplicazione, se si ha un bit 1 basta ripetere il valore dell'altro moltiplicando con lo shift bit di tante posizioni quanto e' il bit del primo moltiplicatore. Un algoritmo ritrovato a questo sito  riporta una variante....invece di spostare l'indice del bit di test viene effettuato sempre il testo sul bit alla posizione 0 (quella piu' sinistra) ma ogni volta viene fatto un bit shift a destra per scorrete tutto il numero. Se il bit in posizione zero e' nullo si fa uno shift a sinistra dell'altro operatore ed uno shift a destra del moltiplicatore. Se il bit alla posizione zero e' 1 allora il valore viene sommato ad una variabile accumulatore



Nessun commento:

Posta un commento