La semplice matematica dietro gli algoritmi di conversione decimale-binario

Se cercate sul web “Come convertire da decimale a binario” troverete quattro semplici algoritmi: due per gli interi e due per le frazioni. Sono presentati con esempi qui sotto nella prima parte dell’articolo, ma mentre il solo conoscere gli algoritmi è quasi sempre sufficiente, ho deciso di provare a capire perché funzionano. Nella seconda parte questo articolo spiega la matematica di base dietro ognuno di essi. Conoscerla può aiutarvi a ricordare qualsiasi algoritmo se improvvisamente lo dimenticate. Vi consiglio vivamente di prendere un quaderno e una penna ed eseguire le operazioni insieme a me per ricordare meglio la matematica.

Convertire un intero decimale in binarioLink a questa sezione

Per convertire un intero in binario, iniziate con l’intero in questione e dividetelo per 2 tenendo presente il quoziente e il resto. Continuate a dividere il quoziente per 2 fino ad ottenere un quoziente di zero. Poi basta scrivere i resti nell’ordine inverso.

Ecco un esempio di tale conversione usando l’intero 12.
Primo, dividiamo il numero per due specificando quoziente e resto:

Ora, dobbiamo semplicemente scrivere il resto in ordine inverso -1100. Quindi, 12 nel sistema decimale è rappresentato come 1100 in binario.

Conversione della frazione decimale in binarioLink a questa sezione

Per convertire la frazione in binario, iniziare con la frazione in questione e moltiplicarla per 2 tenendo conto della parte intera e frazionaria risultante. Continua a moltiplicare per 2 fino ad ottenere una parte frazionaria risultante uguale a zero. Poi basta scrivere le parti intere dai risultati di ogni moltiplicazione.

Ecco un esempio di tale conversione usando la frazione 0,375.

Ora, scriviamo solo la parte intera risultante ad ogni passo – 0,011. Quindi, 0,375 nel sistema decimale è rappresentato come 0,011 in binario.

Convertire l’intero binario in decimaleLink a questa sezione

Per convertire l’intero binario in decimale, iniziate da sinistra. Prendete il vostro totale attuale, moltiplicatelo per due e aggiungete la cifra attuale. Continua fino a quando non ci sono più cifre rimaste.Ecco un esempio di tale conversione usando la frazione 1011.

Convertire la frazione intera in decimaleLink a questa sezione

Per convertire la frazione binaria in decimale, iniziate da destra con il totale di 0. Prendete il vostro totale attuale, aggiungete la cifra attuale e dividete il risultato per 2. Continuate fino a quando non ci sono più cifre rimaste. Ecco un esempio di tale conversione usando la frazione 0.1011. Ho semplicemente sostituito la divisione per 2 con la moltiplicazione per 1/2.

Ecco 4 semplici algoritmi che vi permetteranno di convertire numeri binari in decimali e viceversa.

Espansione base-q di un numeroLink a questa sezione

La chiave per capire perché questi algoritmi funzionano è un base-q expansion di un numero. Un numero intero in qualsiasi sistema numerico può essere rappresentato nella forma seguente:

dove,

  • N è un numero intero
  • x è la cifra (da 0 a 9 per il sistema in base 10, 0 e 1 per il sistema in base-2)
  • q è il valore della base (10 per il sistema in base-10, 2 per il sistema in base-2)

In tutto questo articolo questo modulo è indicato come base q expansion of the number N, o semplicemente base q expansion. Vediamo come si presenta il numero 12 nei sistemi decimale e binario:

Similmente, un numero frazionario in qualsiasi sistema numerico può essere rappresentato nella forma seguente:

dove,

  • N è una frazione
  • x è la cifra (da 0 a 9 per il sistema in base 10, 0 e 1 per il sistema in base-2)
  • q è il valore della base (10 per il sistema in base-10, 2 per il sistema in base-2)

Per il numero 0.375 nei sistemi decimale e binario la rappresentazione è la seguente:

Conversione da decimale intero a binarioLink a questa sezione

A quanto pare, possiamo usare questa forma di espansione base-q per convertire un numero dal sistema decimale a quello binario. Facciamolo per lo stesso numero 12. Per prima cosa, facciamo finta di non sapere come è rappresentato in binario e scriviamolo con le cifre sconosciute sostituite con x:

Il nostro compito è trovare tutte le x. La prima cosa che dobbiamo notare qui è che tutte le sommatorie tranne l’ultima saranno numeri pari, perché sono tutte multipli di due. Ora, usando questa informazione possiamo dedurre la cifra per x0 – se l’intero che viene convertito è pari, allora x0 è uguale a 0, se è dispari – allora x0 deve essere 1. Qui abbiamo il numero 12 che è pari, quindi x0 è zero. Scriviamo queste informazioni:

In seguito, dobbiamo trovare il valore di x1. Poiché tutte le sommatorie da x1 a xN sono multipli di due, possiamo sottrarre il fattore 2 per individuare solo x1. Facciamolo:

È anche facile vedere che la somma dei valori dentro le parentesi è uguale a 6. Quindi, possiamo scrivere il nostro primo passo come:

Continuiamo a trovare le altre x. Possiamo scrivere il polinomio all’interno della parentesi come dichiarazione separata:

Qui, applicando la stessa logica di cui sopra possiamo vedere che x1 è uguale a 0. Riscriviamolo e fattorizziamo di nuovo 2:

Quindi, il nostro secondo passo è:

Ora, possiamo vedere un modello. Possiamo continuare a fattorizzare 2 fino a quando il quoziente è zero. Seguiamo questo schema e vediamo cosa otteniamo.

Siccome il quoziente è uguale a 1, rimane solo un sommando, quindi riscriviamo l’espressione precedente:

Quindi, il nostro terzo passo è:

Quindi, ci ritroviamo con quanto segue:

È chiaro che x3 è uguale a 1. Ma, dato che per il nostro algoritmo abbiamo bisogno di un quoziente, riscriviamo l’espressione precedente in modo che abbia un quoziente:

Siccome ci ritroviamo con il quoziente di 0, non c’è altro da fare e questo era il nostro ultimo passo. Scriviamolo:

Ora abbiamo finito la conversione. Ecco come appare la nostra conversione per passi:

È chiaro ora che il resto in ogni passo corrisponde al valore delle x nelle posizioni corrispondenti: primo resto corrisponde alla prima x, secondo resto alla seconda x e così via. Quindi il numero 12 in binario usando l’algoritmo descritto sopra è rappresentato come 1100.

Ricordiamoci che siamo partiti con l’idea di mostrare perché l’algoritmo che prevede l’immersione per 2 funziona. Prendiamo i passi descritti sopra e spostiamo il 2 nella parte sinistra delle espressioni:

In questo modo potete vedere come siamo arrivati all’algoritmo descritto all’inizio. Possiamo anche mettere i calcoli per quei quattro passi in una rappresentazione come questa

Assicuratevi di capire come siamo arrivati a questa rappresentazione perché ne avremo bisogno quando esploreremo come funziona l’algoritmo di conversione da binario a decimale.

Conversione della frazione decimale in binarioLink a questa sezione

Per mostrare perché moltiplichiamo per 2 e prendiamo la parte intera quando convertiamo le frazioni in binario, userò anche la forma di espansione base-q per le frazioni. Userò il numero frazionario 0,375 dalla prima parte dell’articolo. Analogamente alla parte intera, facciamo finta di non sapere come è rappresentato questo numero in binario e scriviamolo con le cifre sconosciute sostituite da x:

Come per gli interi, il nostro compito è trovare tutte le x individuando le x. Vediamo come possiamo farlo. La prima cosa da notare qui è che le potenze negative di 2 ci danno frazioni con denominatore 2 con potenze positive. Riscriviamo l’espressione di cui sopra:

È immediatamente ovvio che possiamo semplicemente fattorizzare 1/2 nella parte destra dell’espressione. Facciamolo:

e possiamo quindi spostare 1/2 nella parte sinistra

Ok, qui abbiamo individuato x1, e sappiamo che può essere o 1 o 0. Per determinare quale cifra ha, diamo un’occhiata alle somme rimanenti:

Pensiamo a quanto può essere grande la somma di questi numeri. Se il numero massimo di x cifre è 1, allora possiamo semplicemente sostituire le x con 1 e scrivere la somma come:

Bene, questa è una serie geometrica di frazioni, e la somma di tale serie sta nei limiti, quindi il numero massimo che tale somma può darci è 1. Guardiamo ora di nuovo la nostra espressione:

Ora, qui dovrebbe essere chiaro che se il lato destro è minore di 1, allora x1 non può essere uguale a 1 e quindi è uguale a 0, mentre la parte rimanente è uguale a 0,75.

Questo sembra esattamente come il primo passo dell’algoritmo presentato all’inizio:

Togliamo la parte frazionaria di 0.75 e fattorizziamo un altro 1/2 per escludere x2:

e spostiamo 1/2 a sinistra:

Ora, se x2 è uguale a 0, allora la somma del lato sinistro dell’espressione non può essere maggiore di 1, ma il lato sinistro è 1.5, quindi x1 deve essere 1 e la parte rimanente 0,5. Scriviamolo:

Anche questo segue lo schema dell’algoritmo presentato all’inizio:

Ripetiamo le stesse azioni per la restante parte frazionaria di 0.5.

Utilizzando la stessa logica di cui sopra possiamo vedere che x3 è uguale a 1 e non c’è nessuna parte frazionaria rimanente:

Siccome la parte frazionaria rimanente è uguale a 0, ecco come appare il nostro ultimo passo:

Scriviamo di nuovo tutti i passi:

Questo è esattamente l’algoritmo che ho presentato all’inizio. Proprio come abbiamo fatto con i numeri interi, possiamo anche mettere i calcoli per questi tre passi in una rappresentazione come questa:

Ancora una volta, è importante che comprendiate pienamente questa rappresentazione perché ne avremo bisogno quando esploreremo la conversione da binario a decimale.

Perché non tutte le frazioni possono essere rappresentate finitamente in binarioLink a questa sezione

Il fatto che alcune frazioni rappresentate finitamente nel sistema decimale non possono essere rappresentate finitamente nel sistema binario è una sorpresa per molti sviluppatori. Ma questa è esattamente la confusione che sta alla radice dell’apparentemente strano risultato di aggiungere 0,1 a 0,2. Quindi cosa determina se una frazione può essere rappresentata in modo finito in un sistema numerico? Bene, perché un numero sia rappresentato in modo finito, il denominatore di una frazione deve essere una potenza della base del sistema. Per esempio, per il sistema in base 10, il denominatore dovrebbe essere una potenza di 10, ecco perché possiamo rappresentare finitamente 0.625 in decimale:

e non possiamo rappresentare finitamente 1/3:

Lo stesso vale per il sistema in base 2:

Ma se controlliamo 0.1, il denominatore è 10 e non è una potenza di 2, quindi 0,1 sarà una frazione infinita nel sistema binario. Vediamolo usando l’algoritmo che abbiamo imparato sopra:

Possiamo continuare a farlo all’infinito, ma scriviamolo come frazione continua periodica:

Conversione dell’intero binario in decimaleLink a questa sezione

Utilizzerò lo stesso intero binario 1011 della prima sezione per mostrarvi perché l’algoritmo della moltiplicazione per 2 funziona. Qui useremo anche la forma di espansione in base Q del numero. Scriviamolo in questa forma:

Siccome tutti i sommatori sono multipli di 2, possiamo continuare a fattorizzare 2 finché il quoziente è zero. Facciamolo:

Ora, se seguite semplicemente l’ordine delle operazioni matematiche vi ritroverete esattamente con gli stessi passi che ho mostrato all’inizio, in particolare:

In questo modo 1011 in binario è 11 in decimale.

Conversione della frazione binaria in decimaleLink a questa sezione

Ora siamo arrivati all’ultimo algoritmo. Probabilmente, avete già capito da soli la meccanica che c’è dietro. Se no, vediamo perché funziona. La forma di espansione base-q del numero è la chiave anche qui. Prendiamo il numero 0,1011 dalla prima sezione. Scriviamolo nella forma espansa:

Ancora una volta, dato che tutti i sommatori sono multipli di 1/2, possiamo continuare a fattorizzare 1/2 finché non rimane nessuna parte frazionaria. Facciamolo:

Seguendo l’ordine delle operazioni matematiche si ottiene l’algoritmo descritto all’inizio:

In questo modo 0.1011 in binario è 0,6875 in decimale.

Discutere con la comunità

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *