Considerate la seguente funzione:
int f(int x) { if(!x) return 0; return (x%2)+f(x/2); }Tale funzione viene eseguita su tutti i valori di x compresi fra 100 e 500.
Chiamate a il minimo valore ottenuto in queste esecuzioni, e b il massimo valore; quanto valgono a e b?
Soluzione: a=1, b=8.
Osserva
- f(100) = 0+f(50) = 0+0+f(25)= 0+0+1+f(12) = 0+0+1+0+f(6) = 0+0+1+0+0+f(3) = 0+0+1+0+0+f(3) = 0+0+1+0+0+1+f(1) = 0+0+1+0+0+1+1+f(0) = 0+0+1+0+0+1+1+0 = 3
- …
- f(255) = 1+f(127) = 1+1+f(63) + 1+1+1+f(31) = 1+1+1+1+f(15) = 1+1+1+1+1+f(7) = 1+1+1+1+1+1+f(3) = 1+1+1+1+1+1+1+f(1) = 1+1+1+1+1+1+1+1+f(0) = 1+1+1+1+1+1+1+1+0 = 8
- f(256) = 0+f(128) = 0+0+f(64) = 0+0+0+f(32) = 0+0+0+0+f(16) = 0+0+0+0+0+f(8) = 0+0+0+0+0+0+f(4) = 0+0+0+0+0+0+0+f(2) = 0+0+0+0+0+0+0+0+f(1) = 0+0+0+0+0+0+0+0+1 = 1
- …
La funzione restituisce il numero di cifre 1 nella rappresentazione in base 2 di x.
Il prossimo intero con f(n)=9 è 511 …