Newsgroup: it.comp.lang.c++
Titolo: Sapere se un numero è una potenza di 2

Ciao a tutti!
Come posso fare per sapere se un certo numero è una potenza di 2?
Grazie.
Riccardo.

 Come posso fare per sapere se un certo numero č una potenza di 2?
controlli che il suo logaritmo in base 2 sia intero, ad es.
Tra i tanti modi (sicuramente non il migliore):
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  int n, lint, pot;
  double l2;
  cin >> n;
  l2=log(double(n))/log(2.0);  // trovi il log2 di n
  lint=int (l2);  // prendi la parte intera
  pot = n- int (pow(2,double (lint))); 
 if  (pot==0)
 cout << n << " e` potenza di 2: " << "2^" << l2 << endl;
 else
  cout << n << " non e` potenza di 2\n";
}
ciao,
-- 
salvo

 Come posso fare per sapere se un certo numero è una potenza di 2?
per evitare di rispondere in modo banale provo di riportare una soluzione un
pochino piu' creativa:
bool IsPowerOfTwo(unsigned int n)
{
      int c=0;
      for(;(c<2)&&(n);++c,n&=n-1);
      return((c==1)?(true):(false));
}
Tommy

 Tommy
o piu' semplicemente ancora:
bool IsPowerOfTwo(unsigned int n)
{
     if(!n)
          return false;
     else
          return(!(n&=n-1))?(true):(false);
}
in effetti sopra c'e' roba che non e' strettamente necessaria....
questo modo e' anche estremamente efficiente, ovvio, funziona solo per
interi unsigned (positivi).
In pratica su di una macchina con sizeof(int) == 4, una normale macchina a
32 bits, funziona per:
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
2^11 = 2048
2^12 = 4096
2^13 = 8192
2^14 = 16384
2^15 = 32768
2^16 = 65536
2^17 = 131072
2^18 = 262144
2^19 = 524288
2^20 = 1048576
2^21 = 2097152
2^22 = 4194304
2^23 = 8388608
2^24 = 16777216
2^25 = 33554432
2^26 = 67108864
2^27 = 134217728
2^28 = 268435456
2^29 = 536870912
2^30 = 1073741824
2^31 = 
2147483648
tutti questi numeri hanno la particolarita' di avere un solo bit ad 1 e
tutti gli altri a 0, questo grazie al fatto che i computer funzionano in
base 2...
Quindi sfruttando la rappresentazione binaria il calcolo e' semplice ed
efficiente.
Tommy

 }
Credo che questo sia il massimo della compattezza di codice:
inline bool IsPowerOfTwo(unsigned int n)
{
     return(n&&!(n&=n-1));
}
scusate ma quando non riesco a dormire mi diverto a fare queste cose!!!
Tommy

 salvo
Bravo! Vedo che ormai ti sei lanciato nella programmazione C++ !

 Bravo! Vedo che ormai ti sei lanciato nella programmazione C++ !
grazie, sě :)
Anche se la funzione binaria suggerita da Tommy č migliore, la risposta
mi č venuta di getto, pensando ai logaritmi :)
Ho un pizzico di nostalgia di C, ma non rimpiango i printf, scanf,
sprintf ecc. :))
C++ lo trovo piů intuitivo, ma non posso negare che le letture sul C mi
siano servite molto.
Ora devo adattare e affinare le techniche al modo "Stroustruppiano" :)
ciao,
-- 
Salvo

 Come posso fare per sapere se un certo numero è una potenza di 2?
n&&!(n&n-1)
controlli che n non sia uguale a 0 (siamo arrivati fino alla prima n della
espressione), e che (questo 'e' sono gli &&) n&n-1 faccia zero. Se n&n-1 fa
zero vuole dire che c'era un solo bit a attivo, il resto erano tutti a 0;
questa e' la parte !(n&n-1).
Tommy

 ha scritto nel messaggio
news:cg64sh$jm0$1...@titan.btinternet.com...

Grazie mille, mi sei stato utilissimo!
Riccardo Rossi.

 Ora devo adattare e affinare le techniche al modo "Stroustruppiano" :)
ciao.

 logica...
sì, man mano che studio li trovo, hi.
Ma considerando che si è sin dall'inizio posto vari obiettivi, tra cui
essere un superset del C che riscrivesse un linguaggio più efficiente è
anche normale.
Passo dopo passo, intanto cominciamo :)
ciao,
Salvo

 migliore.
Piu' che esperienza di programmazione, semplice conoscenza del sistema
binario. Se hai un minimo di dimestichezza ti si dovrebbe subito accendere
la lampadina delle operazioni bit a bit con questi problemi basatu sulle
potenze di 2.
Ciao.

 :)
Dipende da come vuoi usare quella funzione...se la richiami moltissime volte
di rendi conto quanto il sistema di Tommy sia piu' vantaggioso.

 di rendi conto quanto il sistema di Tommy sia piu' vantaggioso.
infatti, avevo proprio detto "dipende dall'uso che se ne deve fare" :)
ciao,
Salvo

 :)
Molta gente scrive programmi contenenti errori clamorosi e malfunzionanti
(errori logici) per il solo gusto di ottenere programmi a loro dire "veloci"
o come va più di moda "ottimizzati".
La scelta tra una soluzione efficente e una meno non dipende solo
dall'esperienza ma anche dall'estro, dalla interdisciplinarità, dalla
fantasia, insomma è quasi un'arte. Non tutti hanno queste doti, di scrivere
da subito, l'algoritmo più efficiente.
Io ad esempio non ho questa dote.
Però possiamo comunque anche noi (scusa se ti associo per un attimo a me)
scrivere programmi che funzionano ugualmente bene. Se poi il programma che
facciamo perderà molto tempo e questo dovesse diventare un problema, allora
si va ad intervenire sulla parte che da dei problemi. Spesso il tempo
d'esecuzione del programma sta per il 95% nel 2% del codice che hai scritto.
Se saprai scrivere una funzione nel modo più brillante, allora tanti
complimenti, se non ci riuscirai ma questa verrà chiamata una sola volta,
nessuno se ne accorgerà e comunque darà il suo corretto risultato. Se le
esigenze cambiano e dovrai richiamarla un milione di volte e vedi
rallentamenti, allora ti rimbocchi le maniche (o meglio spremi le meningi) e
trovi qualche sistema migliore.
E' carina l'intuizione di Tommy, è sicuramente il modo più giusto,
complimenti a chi ha queste trovate (io non ci avevo pensato, ma ho già
detto di non essere il programmer più veloce del West), però non ci si deve
fustigare se al primo colpo non ci vengono brillanti soluzioni. Sicuramente
se richiami la tua funzione un milione di volte, poi viene in mente anche a
te (a me è già successo più di una volta con mie classi o funzioni) che devi
rimetterci le mani. La differenza però è che se devi mettere le mani su di
un programma che funziona è una cosa, se invece ci sono diversi errori
allora certe volte si fa prima a riscrivere tutto da capo. L'ideale è
scrivere buon sofware efficiente (come alcuni, tra cui Tommy fanno), se per
qualche motivo non dovesse essere il massimo dell'efficienza, almeno che sia
un buon sofware (puoi sempre contare di migliorarlo le prestazioni diventano
una criticità, una buona programmazione ad oggetti dovrebbe consentire
questo).
ciao.

 questo).
Ecco, su questo adesso mi vorrei esercitare, dopo tanto tempo passato su
programmi "sequenziali" e strutturati.
ciao,
salvo