Ragiona:
1) il numero in base 10 e' un intero o un numero con la virgola? -> supponiamo che sia un numero intero
2) ora, supponiamo che lo leggi dalla tastiera (con la "scanf"). Cisono due casi: 2) lo leggi come stringa (quindi una stringa che descrive un numero in base 10) oppure direttamente come numero.
3) supponiamo che lo leggi come numero (intero!)
4) ora in memoria hai il numero intero scritto in base 10 sulla console, E RAPPRESENTATO IN BASE 2 in memoria (i computer usano la rappresentazione binaria, come saprai )
Quindi il tuo bel 17 (in decimale) e' rappresentato come 10001 (in base 2)
5) ora facciamo un passo in piu': il tuo numero e' memorizzato in una variable di tipo intero.
In C ci sono diversi tipi di interi, classificabili in base a 2 parametri:
a) se con o senza segno (keyword 'signed', che e' il default, oppure 'unsigned')
b) dal numero di bit: char, short, int, long, long long
Qui' purtroppo il C non e' mai stato chiaro e il numero di bit per i vari tipi di intero dipende dalla piattaforma (8/16/32/64 bit) e dal compilatore. Supponiamo la situazione piu' comune
char -> 8 bit
short -> 16 bit
int -> 32 bit
long -> 32 bit
long long -> 64 bit
NOTA: I nuovi compilatori C/C++ introducono, finalmente, anche i simboli int8_t, int16_t, int32_t, int64_t ed eventualmente in128_t, e le loro controparti 'unsigned'
Ora, diciamo che il tuo numero sia memorizzato in una varabile di tipo 'int'. Quindi 32 bit.
Quindi il tuo 17 non e' 10001, ma piu' precisamente:
00000000 00000000 00000000 00010001
(ogni blocchetto sono 8 bit)
6) ed addesso un'altro passo: in C ci sono tutta una serie di operatori 'bit based', cioe' che ti permettono di manipolare i singoli bit di un intero.
& -> and
| -> or
~ -> not
>> -> shift a destra
<< -> shift a sinistra
>>> -> arithmetic shift.
7) e qui' sta' il bello: che cosa rappresenta uno shift? A seconda della direzione, una moltiplicazione per 2 o una divisione per 2
a questo punto hai sufficienti informazioni per calcolare il logaritmo in base due di un intero.
Hai a disposizione almeno 2 approcci, uno facile e un leggermente meno facile (ma solo un'epsilon). Anzi 3
a) se inizi da SINISTRA, ti basta trovare la PRIMA posizione un cui un bit NON E' 0
b) se inizi da DESTRA, ti basta trovare l'ULTIMA posizione un cui un bit NON E' zero
c) (la piu' facile) che cosa succede se fai uno shift a destra di 1 bit del tuo numero?
00000000 00000000 00000000 00010001
diventa
00000000 00000000 00000000 00001000
(nota che il n di bit NON CAMBIA) ti sei mangiato un bit!
Ma se ti mangi tutti i bit a 1, che cosa resta? UN numero in cui TUTTI I BIT sono a 0.
Ma un intero con TUTTI I BIT a 0, che numero e'? E' ZERO!!!!
Quindi ti basta shiftare il tuo numero di un bit alla volta a destra fino a che non diventa ZERO!
NOTA: con che operatre? ">> oppure ">>>"?
Il numero di shift che hai fatto e' il tuo logaritmo in base 2 del tuo numero.
ATTENZIONE: e se il numero e' negativo? Il logaritmo di un numero negativo ESISTE, e' un numero complesso, ma comunque puoi calcolarlo lo stesso con qualche trasformazione!