[ALGORITMO] Dato un numero, fra quali potenze di 2 si trova?

[netarrow]

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 ) quindi se qualcuno mi aiuta mi fa un grosso favore!

ciao e grazie

[oregon]

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]

grazie, anche questo può andare

Scusa un attimo, log sarebbe logaritmo? E int?

[oregon]

Int = parte intera

Log = logaritmo in base e

[netarrow]

ok grazie, l'avevo interpretato come un cast.

[oregon]

Tu non hai specificato il linguaggio con cui volevi lavorare ...

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

[netarrow]

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.