Passaggio numero decimale-binario...
Carissimi ragazzi, nel corso di una lezione di Calcolo Numerico I, il docente ha presentato un algoritmo, in linguaggio C, capace di trasformare un numero rappresentato in base 10 in un numero rappresentato in base 2, by-passando il problema delle divisioni successive. L'algoritmo che abbiamo implementato è il seguente (stando ai dettami del docente):
Il problema è che provandolo con un normale devC++ non mi si restituisce il risultato corretto eppure non riesco a comprendere dove sia l'errore, dal momento che il "modello carta e penna" conferma la bontà di tale algoritmo.
Inoltre se non "shifto" inv mi vien restituito il risultato corretto a meno dell'orientamento (perdonate l'abusa di linguaggio
). Ringrazio sentitamente per la collaborazione. 
#include<stdio.h>
main()
{
int n, inv, r;
scanf("%d",&n);
inv=0
do{
r=n&1;
inv=(inv<<1)|r;
n=n>>1;
}while(n!=0);
printf("%d",inv);
}
Il problema è che provandolo con un normale devC++ non mi si restituisce il risultato corretto eppure non riesco a comprendere dove sia l'errore, dal momento che il "modello carta e penna" conferma la bontà di tale algoritmo.
Inoltre se non "shifto" inv mi vien restituito il risultato corretto a meno dell'orientamento (perdonate l'abusa di linguaggio
). Ringrazio sentitamente per la collaborazione.
Risposte
"menale":
Carissimi ragazzi, nel corso di una lezione di Calcolo Numerico I, il docente ha presentato un algoritmo, in linguaggio C, capace di trasformare un numero rappresentato in base 10 in un numero rappresentato in base 2, by-passando il problema delle divisioni successive.
by-passando che parolona
#include<stdio.h>
main()
{
int n, inv, r;
scanf("%d",&n);
inv=0
do{
r=n&1;
inv=(inv<<1)|r;
n=n>>1;
}while(n!=0);
printf("%d",inv);
}
l'algoritmo utilizza gli operatori bit-wise del C.
Gli operatori di shift di una posizione sono equivalente a moltiplicare (shift sinistro) e dividere (shift sinistro) perciò sono equivalenti alle moltiplicazioni/divisioni successive
Il problema è che provandolo con un normale devC++ non mi si restituisce il risultato corretto eppure non riesco a comprendere dove sia l'errore, dal momento che il "modello carta e penna" conferma la bontà di tale algoritmo.
Inoltre se non "shifto" inv mi vien restituito il risultato corretto a meno dell'orientamento (perdonate l'abusa di linguaggio
bhe se è una base diversa non puoi pensare di stampare un decimale (%d) se è rappresentato in binario dopo la conversione. (tralasciando che un calcolatore lavora già in binario perciò il decimale $n$ è intrisecamente un numero binario).
PS: questo è un argomento che starebbe meglio in Informatica
"hamming_burst":
by-passando che parolona
Ogni tanto bisogna farne uso!
"hamming_burst":
bhe se è una base diversa non puoi pensare di stampare un decimale (%d) se è rappresentato in binario dopo la conversione. (tralasciando che un calcolatore lavora già in binario perciò il decimale n è intrisecamente un numero binario).
Cosa mi consigli di fare in merito?
"hamming_burst":
PS: questo è un argomento che starebbe meglio in Informatica
Te ne do atto!
P.S.
"hamming_burst":
l'algoritmo utilizza gli operatori bit-wise del C.
Gli operatori di shift di una posizione sono equivalente a moltiplicare (shift sinistro) e dividere (shift sinistro) perciò sono equivalenti alle moltiplicazioni/divisioni successive
La spiegazione non era richiesta
Ovviamente si scherza
ok. prima pensavo fosse un errore nel comprendere la "stampa" cioè che te non avessi considerato che ciò che stampi è il numero stesso. Ma vedo che è l'algoritmo non funziona.
Prima c'è un piccolo errore di sintassi:
mancava il $;$
Ho provato velocemente ad applicarlo al numero $10$ ma non funziona (per questo numero manca uno schift)
per il numero $5$ funziona così com'è. Per potenze di $2$ tale codice non ha senso.
Dimmi un po' cosa ti ha detto il docente, così comprendo perchè lo hai interpretato in questo modo il code, che ora non ho molta voglia di cercar l'errore
Prima c'è un piccolo errore di sintassi:
inv=0;
mancava il $;$
Ho provato velocemente ad applicarlo al numero $10$ ma non funziona (per questo numero manca uno schift)
per il numero $5$ funziona così com'è. Per potenze di $2$ tale codice non ha senso.
Dimmi un po' cosa ti ha detto il docente, così comprendo perchè lo hai interpretato in questo modo il code, che ora non ho molta voglia di cercar l'errore
"hamming_burst":
Prima c'è un piccolo errore di sintassi:
CODICE: SELEZIONA TUTTO
inv=0;
Sìsì, è stato un mio errore di battitura!
"hamming_burst":
Dimmi un po' cosa ti ha detto il docente, così comprendo perchè lo hai interpretato in questo modo il code, che ora non ho molta voglia di cercar l'errore
In realtà questo è il codice che c'è su delle fotocopie date dal docente stesso!
"menale":
In realtà questo è il codice che c'è su delle fotocopie date dal docente stesso!
se puoi, mostrami questa fotocopia.
Comunque per me questo algoritmo è inutile, cioè non riesco a pensare ad un'utilià pratica.
Praticamente si prende il numero decimale, si utilizza la sua rappresentazione binaria (?) del decimale, si utilizzano operatori binari e per cosa? per riproporre lo stesso numero binario in un altro identificatore.
E' solo ""interessante"" come proposta didattica.
L'obiettivo sarebbe, teoricamente, quello di restituire la scrittura binaria del numero!
Spero sia chiara l'immagine!
P.S. Non so perché sia venuta fuori così grande!?!
ah ok ho capito l'errore.
Non vedi ciò che è stato calcolato perchè semplicemente si itera al contrario (diciamo che è simile alla problematica big-endian little-endian).
L'utilità del codice è tipo per iterare su bit utilizzando gli operatori di bitwise. Si utilizza spesso per velocizzare le operazioni, scritto in questo modo non lo avevo mai visto, mi tornerà utile.
Prova a vedere cosa ti stampa:
codice equivalente (cioè iterare sui bit) che ho ancora utilizzato:
cosa ti stampa?
Non vedi ciò che è stato calcolato perchè semplicemente si itera al contrario (diciamo che è simile alla problematica big-endian little-endian).
L'utilità del codice è tipo per iterare su bit utilizzando gli operatori di bitwise. Si utilizza spesso per velocizzare le operazioni, scritto in questo modo non lo avevo mai visto, mi tornerà utile.
Prova a vedere cosa ti stampa:
inv=0
do{
r=n&1;
if(r) printf("1");
else printf("0");
n=n>>1;
}while(n!=0);
codice equivalente (cioè iterare sui bit) che ho ancora utilizzato:
while(inv<=ceil(log2(n))){
if(n&((int)pow(2,inv))){
printf("1");
}
else printf("0");
inv++;
}cosa ti stampa?
Stesso errore: mi reca il numero in binario a ritroso
"menale":
Stesso errore: mi reca il numero in binario a ritroso
bhe è quello che ho scritto...
è dovuto al fatto che si parte ad itereare dal bit in posizione $0$ invece che quello più significativo. Non ha caso ho scritto che è simile alla problematica di endianness.
Per far sì che il codice riporti il numero corrispondente, bisogna sporcare un po' il codice con operatori non-bitwise.
Dobbiamo conoscere quanti di bit servono per rappresentare il numero, per darci un limite superiore su cui fermarsi.
Es. $(5)_10 = (101)_2$ cioè servono $3$ bit. Ovviamente parliamo di numero senza segno. Anzi è più corretto nel codice tipizzare gli interi con unsigned int. Non ha nessun senso il codice con tipi negativi.
Per conoscere il numero di bit di rappresentazione bisognerebbe utilizzar il logaritmo in base due, ma non mi piace molto l'idea. Perciò ci igegniamo un attimo ed aggiungiamo un iteratore in più. Perciò:
unsigned int n, inv,r,i;
r=inv=i=0;
scanf("%d",&n);
i=n;
r=0;
while(i>>=1){ //conoscere il numero di bit di rappresentazione
r++;
}
i=1<<r; //inizializzo il bit più significativo
inv=0;
do{
inv = inv^(n&i); //XOR od OR non cambia
}while(i>>=1);
printf("%d\n",inv);così abbiamo il numero nell'ordine corretto, ma bisogna "pagare" un ciclo (inesistente come costo) in più.
se hai domande chiedi pure
Sarebbe stato più bello girare il numero in-place, ma non trovo un metodo generale (solo per piccoli casi tipo con $4$ bit).
Cosa si intende per
?
i>>=1
?
"menale":
Cosa si intende per
i>>=1
?
semplicemente è una scrittura contratta per:
i = i >> 1
chiamasi zucchero sintattico, è per rimanere sintetici con un codice di poche righe.
EDIT: forse non essendoti familiari quegli accrocchi sintattici, ti è più semplice questo codice esteso:
unsigned int n, inv,r,i;
n=inv=r=i=0;
scanf("%d",&n);
i=n;
r=0;
while(i!=0){
r++;
i = i>>1;
}
i=1<<r;
inv=0;
do{
r = n&i;
inv = inv|r;
i = i>>1;
}while(i!=0);
printf("%d\n",inv);
Della serie i++ che sta per i=i+1?
"menale":
Della serie i++ che sta per i=i+1?
sì esatto.
MI tracceresti li linee guida con cui hai definito l'ultimo algoritmo?
"menale":
MI tracceresti li linee guida con cui hai definito l'ultimo algoritmo?
Da questa tua domanda desumo tu non sappia cosa sia il bit più significativo o la problematica endianness.
Vediamo di esser più chiari:
Qualunque base numerica si basa sulla "rappresentazione posizionale". Un insieme di scatolette numerate che vengon occupate dai vari numeri:
_ _ _ _ _
4 3 2 1 0
es. il numero $(29)_{10}$:
2 9
1 0
il numero $(11101)_2$
1 1 1 0 1
4 3 2 1 0
che corrispondono alle potenze delle varie basi:
$(11101)_2 = 1*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = (29)_{10}$
(una riscrittura alternativa: sia $d in {0,1}$ allora \(〚d\{0,1\}〛= 2*〚d〛+ \{0,1\}\))
in generale $(h_n h_(n-1) ... h_1 h_0)_b = \sum_{i=0}^{n} h_i*b^i$
penso sia risaputo questo, ma meglio esser chiari di cosa si parla
Veniamo all'algoritmo.
Il tuo parte ad analizzare il codice dalla scatoletta numero $0$ e va in crescendo, utilizzando gli operatori di bitwise salva in inv il numero rovesciato. Ma ciò comporta che la rappresentazione posizionale binaria sia contraria perciò la controparte decimale ha significato differente:
\( n(29)_{10} = (11101)_{2} \rightleftarrows (10111)_2 = inv(23)_{10}\)
Ora con la mia proposta parte dalla posizone del bit più significativo (nell'esempio sarebbe scatoletta $4$). Il problema è che non siamo oracoli e non possiamo indovinare dove sia la posizione di questo bit perchè ogni numero decimale ha la sua rappresentazione binaria. Perciò dobbiamo calcolare dove sia con un algoritmo aggiuntivo.
Da un punto di vista di analisi sarebbe semplicemente il ceiling del logaritmo in base $2$ (penso tu sappia il perchè...).
Noi invece che utilizzare il logaritmo, visto che si utilizzano operatori bit-wise utiliziamo un metodo basso livello con un semplice iteratore e contiamo quante posizioni ci stanno dal bit più significativo alla posizione $0$.
In codice shiftiamo il bit più significativo fino a $0$ e ad ogni iterazione aggiorniamo un iteratore.
$i(...11101)$ i=i>>1 r=0
$i(...01110)$ i=i>>1 r=1
...
$i(...00000)$ i=i>>1 r=4 e si esce dal ciclo perchè $i=0$. Perciò si ha $5$ bit di rappresentazione
EDIT:
Poi semplicemente ci inizializziamo $i$ con l'informazione che abbiamo calcolato cioè sapere dove sta il bit più significativo:
i=1<<r (10000)
poi bhe è il semplice contrario del tuo algoritmo. Controllo ad ogni iterazione se il bit che sto analizzando è attivo o meno con l'AND e aggiorno inv con l'informazione trovata.
Alla fine avrò il numero uguale a quello che ho inserito.
Vedi se così ti è più chiaro. Il codice è banale, solo la rappresentazione binaria penso ti crei confusione.
Sì l'algoritmo è chiaro, ma resta il fatto che quello di partenza è palesemente legato ad un errore, ossia la restituzione del numero a ritroso.
Ho pensato anche ad un'altra posizione: se creassi un array in cui salvare i resti ottenuti e poi stamparlo a ritroso?
Ho pensato anche ad un'altra posizione: se creassi un array in cui salvare i resti ottenuti e poi stamparlo a ritroso?
"menale":
Sì l'algoritmo è chiaro, ma resta il fatto che quello di partenza è palesemente legato ad un errore, ossia la restituzione del numero a ritroso.
guarda che non è errato. Se non è stato scelto a caso inv sta per inverse... cosa che nei primi post non ci avevo fatto caso
(a dire il vero non proprio l'inverso; l'inverso di quel numero è il complemento ma vabbè...)Quello che fa l'algoritmo è calcolare la rappresentazione binaria e lo fa davvero, sta all'utente capire l'orientamento, almeno dovrebbe esserci un commento che lo spiega.
La cosa sbagliata, se ciò che chi ha scritto il codice è voluto (cioè il numero binario invertito), è che c'è una print del decimale...cosa folle in questo caso. Forse si può pensare che chi lo ha scritto, ha dato per scontato che chi utilizzasse il
codice, sapesse che il numero fosse invertito, perciò quello che doveva stampare doveva essere l'inversa del numero di partenza.
Ma sul tuo testo non c'è uno straccio di commento?? Non penso che si vada a deduzioni, se no è davvero fatto male...
Ho pensato anche ad un'altra posizione: se creassi un array in cui salvare i resti ottenuti e poi stamparlo a ritroso?
bhe se inizi ad utilizzare vettori, divisioni, ecc... l'algoritmo non utilizzerà più operatori bitwise e sarà più costoso. Quello che abbiamo scritto è efficiente e parecchio.
Ma se vuoi farlo per esercizio ben venga, prova a scriverlo qui e se ti serve una mano basta postare
"hamming_burst":
Ma sul tuo testo non c'è uno straccio di commento?? Non penso che si vada a deduzioni, se no è davvero fatto male...
Ahimè non è stato tratto dal testo di riferimento (il Murli), ma fa parte di alcune fotocopie che fan da sintesi del linguaggio C, trattato nel corso di "Laboratorio di programmazione" del primo anno accademico.
"hamming_burst":
bhe se inizi ad utilizzare vettori, divisioni, ecc... l'algoritmo non utilizzerà più operatori bitwise e sarà più costoso. Quello che abbiamo scritto è efficiente e parecchio.
Concordo appieno. In tal modo si perde l'utilità di questo algoritmo.
"hamming_burst":
Ma se vuoi farlo per esercizio ben venga, prova a scriverlo qui e se ti serve una mano basta postare
Ci penserò e continuerò a discuterne in loco!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo