C'è modo di effettuare una divisione per 2 usando solo addizione e/o sottrazione?

[luxorl]

Ciao a tutti.
Svolgevo qualche appello di Calcolatori Elettronici, così giusto per esercitarmi per l'esame ormai vicinissimo.. quando inciampo in un problema in cui un passo consiste di far dividere un numero (ovviamente dopo alcune altre richieste) per 2...

voi a questo punto direte: "Embè? dov'è il problema?"

Il problema sta nel fatto che dobbiamo sfruttare un'architettura di riferimento che utilizza una ALU (Unità Aritmetica Logica) che sa fare solo somma e sottrazione...

ora una variante di quella traccia è che al posto della divisione per 2, c'è la moltiplicazione per 2... qui il problema è risolvibile.. perchè la moltiplicazione si può ricondurre ad una serie di somme.. quindi nel mio caso basto che sommo 2 volte il numero..

ma per la divisione? esiste qualcosa di analogo alla moltiplicazione? se si.. a me sfugge proprio... chi mi da una mano?

Grazie :mano:

[lucio68]

Originariamente inviato da luxorl
Ciao a tutti.
Svolgevo qualche appello di Calcolatori Elettronici, così giusto per esercitarmi per l'esame ormai vicinissimo.. quando inciampo in un problema in cui un passo consiste di far dividere un numero (ovviamente dopo alcune altre richieste) per 2...

voi a questo punto direte: "Embè? dov'è il problema?"

Il problema sta nel fatto che dobbiamo sfruttare un'architettura di riferimento che utilizza una ALU (Unità Aritmetica Logica) che sa fare solo somma e sottrazione...

ora una variante di quella traccia è che al posto della divisione per 2, c'è la moltiplicazione per 2... qui il problema è risolvibile.. perchè la moltiplicazione si può ricondurre ad una serie di somme.. quindi nel mio caso basto che sommo 2 volte il numero..

ma per la divisione? esiste qualcosa di analogo alla moltiplicazione? se si.. a me sfugge proprio... chi mi da una mano?

Grazie :mano:

In maniera assolutamente empirica (e non so quanto corretta), sottrarrei 1 dal dividendo finché non otterrei un numero che aggiunto a se stesso desse come risultato il dividendo stesso.
Ad esempio, se l'operazione iniziale fosse 8:2, farei
8-1=7+7=14
7-1=6+6=12
6-1=5+5=10
5-1=4+4=8

[andrea]

Basta effettuare sottrazioni successive e contare quante ne fai esempio:

14 - 2
12 - 2
10 - 2
8 - 2
6 - 2
4 - 2
2 - 2
0

contate sono 7 e infatti 14/2 fa 7

[luxorl]

Originariamente inviato da andrea
Basta effettuare sottrazioni successive e contare quante ne fai esempio:

14 - 2
12 - 2
10 - 2
8 - 2
6 - 2
4 - 2
2 - 2
0

contate sono 7 e infatti 14/2 fa 7


Ecco La soluzione!!!! :) :D

Grazie mille!!

[gurutech]

Originariamente inviato da luxorl

Il problema sta nel fatto che dobbiamo sfruttare un'architettura di riferimento che utilizza una ALU (Unità Aritmetica Logica) che sa fare solo somma e sottrazione...


niente shift? che architettura :huh:

[Sirio]

Originariamente inviato da gurutech
niente shift? che architettura :huh:
infatti, sicuro che non ci siano shift register? In caso credo si debba risolvere con uno shift.

[Kajok]

come funziona con lo shift? altrimenti io farei la procedura descritta da andrea

[Sirio]

Originariamente inviato da Kajok
come funziona con lo shift? altrimenti io farei la procedura descritta da andrea
con uno shift basta appunto shiftare i bit che rappresentano il numero eliminando il meno significativo, in questo modo si ottiene una divisione mod 2.

Ad esempio:

1010 (BIN) = 10 (DEC)
101 (BIN) = 5 (DEC)

[Ziosilvio]

A pensarci bene, la soluzione sta proprio nell'usare uno shift...

Pensaci un attimo: tu hai un numero x>=0 che puoi scrivere come 2y+z, con z che è o 0 o 1, e vuoi trovare y.
Pensa al problema inverso: tu hai y e z, e vuoi calcolare x=2y+z. Allora che fai? Attacchi uno 0 in fondo a y, il che in base 2 è lo stesso che raddoppiarlo, e poi aggiungi z; oppure, semplicemente, attacchi z in fondo a y.
Ma allora, per trovare y a partire da x, basta togliere la cifra z: e questo si fa con uno shift di una posizione verso destra.

(Se x<0, basta che cambi segno, dividi per 2 col sistema di prima, e cambi di nuovo segno.)

[luxorl]

Originariamente inviato da Sirio
con uno shift basta appunto shiftare i bit che rappresentano il numero eliminando il meno significativo, in questo modo si ottiene una divisione mod 2.

Ad esempio:

1010 (BIN) = 10 (DEC)
101 (BIN) = 5 (DEC)

D'OH :doh:

e chi ci aveva pensato allo shift.. comunque l'ALU che dobbiamo prendere di riferimento lo dovrebbe avere, ma io purtroppo me ne ero completamente dimenticato... :muro: ero troppo concentrato sui tipi di esercizi che hanno fatto vedere durante il corso..

Vabbè meglio ricordarselo prima dell'esame e non dopo :p

Grazie davvero... :)

[Kajok]

Figo lo Shift.... non ci avevo mai pensato!! :muro: :muro:

[khri81]

scusate ma lo shift nn dovrebbe essere proprio l'operazione di divisione e moltiplicazione???

se l'autore del treahd ha detto che la alu nn sa fare divisione e moltiplicazione nn dovrebbe avere lo shift!!!

[luxorl]

Originariamente inviato da khri81
scusate ma lo shift nn dovrebbe essere proprio l'operazione di divisione e moltiplicazione???

se l'autore del treahd ha detto che la alu nn sa fare divisione e moltiplicazione nn dovrebbe avere lo shift!!!

Devo controllare.. però dovrebbe esserci! ho già detto che mi ero sbagliato :)

e comunque lo shift è la div e la mul per 2.. non in generale!
Per esempio dividere per 3 è impossibile con uno shift..

[khri81]

Originariamente inviato da luxorl
Devo controllare.. però dovrebbe esserci! ho già detto che mi ero sbagliato :)

e comunque lo shift è la div e la mul per 2.. non in generale!
Per esempio dividere per 3 è impossibile con uno shift..

si hai ragione ho detto una cazzata ;)

[Sirio]

Non è che l'ALU deve avere uno shift, nell'architettura deve essere presente uno shift register in modo da poter traslare i bit.

[Kajok]

che ALU usi?