Per la moltiplicazione a livello di bit, i computer sfruttano il fatto che è molto facile moltiplicare per 2 in binario.
Vedi, in decimale, moltiplicare per 10 è facile, perché questa è la base del sistema numerico. Se vuoi moltiplicare, per esempio, 56 per 10, tutto quello che devi fare è aggiungere uno zero alla fine e ottieni 560.
Similmente, in binario, diciamo che vuoi moltiplicare 9, che è 1001 espresso in binario per 2. Tutto quello che devi fare è aggiungere uno zero alla fine: La risposta è 10010.
Questo va bene, ma come si fa a moltiplicare per un numero che non è 2? Diciamo che vuoi moltiplicare 9 per 11, cioè 1001 x 1011 in binario. Notate che scrivere 11 in questo modo significa davvero quanto segue:
[math](11)_{10} = (1011)_2 = 1cdot 2^3 + 0cdot 2^2 + 1cdot 2^1 + 1cdot 1^0 = 1cdot 8 + 0cdot 4 + 1cdot 2 + 1cdot 1[/math]
(Tutti i numeri dopo il secondo segno uguale sono in decimale, nel caso non fosse chiaro;chiaro)
Quindi questo significa (per la lav distributiva):
[math]9cdot 11 = 9cdot (8 + 2 + 1) = 9cdot 8 + 9cdot 2 + 9cdot 1[/math]
(Questa volta, tutto è in decimale). Quindi, se solo possiamo trovare i tre termini sul lato destro e sommarli, abbiamo finito. Si scopre che tutte queste moltiplicazioni equivalgono semplicemente ad aggiungere degli zeri in binario:
[math](1001)_2 cdot 1 = (1001)_2[/math]
[math](1001)_2 cdot 2 = (10010)_2[/math]
[math](1001)_2 cdot 4 = (100100)_2[/math]
[math](1001)_2 cdot 8 = (1001000)_2[/math]
(I'ho incluso il caso 4 anche se non è tecnicamente necessario). Ora possiamo sommare i termini rilevanti per ottenere:
[math](1001)_2 cdot (1011)_2 = (1001000)_2 + (10010)_2 + (1001)_2 = (1100011)_2[/math]
Questo è esattamente 99 in decimale.
Questo algoritmo è facile da generalizzare: avete solo bisogno di aggiungere zeri (che a volte è noto come "spostamento", dal momento che siete fondamentalmente spostando tutte le cifre a sinistra) e aggiungere.
Questo può sembrare arcano al giorno d'oggi, ma io l'ho effettivamente implementato nel linguaggio assembly del Commodore 64, dato che il processore non aveva operazioni di moltiplicazione a livello di CPU.
Forse più interessante, sono rimasto piuttosto sconcertato quando ho poi imparato (al liceo) che questo era in realtà esattamente il modo in cui gli antichi egizi facevano la moltiplicazione. Ovviamente, la notazione era diversa, ma è comunque molto bello che abbiano inventato un algoritmo così "moderno" allora.
Per quanto riguarda la divisione, è un po' più complicata, ma è fondamentalmente la stessa della divisione lunga. Lascio a qualcun altro il compito di fare un esempio.