PDA

Visualizza la versione completa : [ALGORITMO] Dato un numero, fra quali potenze di 2 si trova?


netarrow
09-11-2005, 18:52
Ciao a tutti, sto cercando di trovare un modo più "skilloso" di sapere fra quali potenze di 2 si trova un numero, però non facendo un ciclo normale verso il numero o dal numero verso il 2 guardando se è effetivamente una moltiplicazione ripetuta di due, ma giocando sul numero in binario.

Sulla carta ho trovato 2 soluzioni, la prima è questa:

es. 50:

110010

devo annullare tutti gli 1 tranne il primo a sinistra per ottenere appunto la prima tra cui si trova(100000 sarebbe 32 appunto).

Il problema è: come faccio a salvare il primo bit?

Il secondo sistema mi è venuto facendo questo:

1 = 1
11 = 3
111 = 7
1111 = 15
11111 = 31

E visto che aggiungendo un uno il numero aumenta di una potenza di due(1-3 2, 3-7, 4, 7-15, 8, 15-31 16 ecc...)

Ho fatto questo:

110010 = 50

faccio sparire il primo bit a sinistra

10010 = 18

Sottraggo e ottengo 32

Devo praticamente troncare parte del numero dal primo 1 a sinistra al secondo 1 a sinistra, ad esempio

80 = 1010000

diventa 10000 = 16

80 - 16 = 64

Per la potenza a cui precede basta moltiplicare per due quella cui segue però la parte centrale del lavoro(togliere o annullare i bit) riesco a farla soltanto mano, non sono pratico di operazioni bit-a-bit (è per questo che sto facendo sta strada più scervellante :D) quindi se qualcuno mi aiuta mi fa un grosso favore!

ciao e grazie :ciauz:

oregon
09-11-2005, 19:20
Dato il valore x, questo e' compreso tra le potenze di 2 determinate da

2 ^ (Int(Log(x) / Log(2)))

e

2 ^ (Int(Log(x) / Log(2)) + 1)

netarrow
09-11-2005, 19:21
grazie, anche questo può andare :)

Scusa un attimo, log sarebbe logaritmo? E int? :confused:

:ciauz:

oregon
09-11-2005, 19:29
Int = parte intera

Log = logaritmo in base e

netarrow
09-11-2005, 19:31
ok grazie, l'avevo interpretato come un cast.

:ciauz:

oregon
09-11-2005, 19:36
Tu non hai specificato il linguaggio con cui volevi lavorare ...

Te l'ho dato in VB ... ma in c non e' molto diverso ...

netarrow
09-11-2005, 20:55
infatti era un problema di informatica generico, poi visto che a scuola mi fanno pascal l'ho tradotto in quello, se a qualcuno servisse il codice lo posto:



program pot2;
uses crt;

var
x, potPrec:real;

begin
writeln('inserire un numero maggiore di 1');
readln(x);
if x > 1 then
begin
potPrec := exp(LN(2) * (round(LN(x)/LN(2))-1));
writeln(x:0:0, ' si trova fra ', potPrec:0:0, ' e ', potPrec*2:0:0);
readln;
end
else
begin
writeln('Il programma non lavora');
end
end.


:ciauz:

Loading