Newsgroup: it.comp.lang.c
Titolo: Contare gli i bit 1 in una variabile...

Salve quale e' il metodo + veloce x contare gli uno un una variabile?
a me a dire il vero non serve il numero esatto ma solo se sono
maggiori degli zero :)
al momento pensavo di confrontarli con una maschera e shiftare di uno
a destra (equivale a dividere x 2 quindi e' come se facessi diviso 2 e
modulo di 2)...
tipo
for (k=0;k<8;k++) {
	if (n & 1) i++;
	n= n>>1; //dimentico sempre quale e' lo shift a destra :)
}
Che ne dite?
Ciao
--------------------------------------------------
Kirys
Remove DELTHIS from the address to reply
   .  _/\  ______/\ 
  /| /  /  \  _____\     
http://www.kt2k.com
 / |/  /    \/  / \/  _____  _____  _____  _____
/   _  \    /  /     |___  ||     ||     ||     |
\__| \  \  /  /      |  ___||  |  ||  |  ||  |  |
      \_/  \_/       |_____||_____||_____||_____|

 maggiori degli zero :)
se aggiungi un if (i>(sizeof(n)<<1)) e' piu' veloce nel caso devi fare 
molti controlli

 molti controlli
emmm, >> 1, mannaggia alla fretta...

"Kirys" <uniK...@DELTHIShotmail.com> ha scritto nel messaggio
news:tqjdktkm41lim9lnp...@4ax.com...

1) al posto di  n= n>>1 scriverei n >>= 1;
2) per migliorare ancora la velocità va considerato che se gli uni o gli
zeri che hai contato superano la metà del size del registro è inutile
continuare a controllare.
3) Ancora più veloce e di utilizzo generale: per un tipo char (anche con il
tipo short volendo) puoi allocare un array di 256 (65536 per short) char
dove ad ogni posizione viene precalcolata ed assegnata la risposta che ti
serve (usando il numero n come indice dell' array).
----
Sergio Bianchi

 Salve quale e' il metodo + veloce x contare gli uno un una variabile?
Io (in C), non so se questo sia il modo piu' veloce, ma credo sia un ottimo
metodo.
Tra le altre cose mi sembra sia anche citato nei primi capitoli sul K&R.
Alex

 emmm, >> 1, mannaggia alla fretta...
???
Scusa potresti mettermelo in pratica...non lo capisco.
non capisco cosa tu voglia dire.
Dove metteresti:
if (i>(sizeof(n)>>1))
e a cosa servirebbe ?
Alex

 serve (usando il numero n come indice dell' array).
Per prima cosa la funzione non "calcolerebbe" ma "leggerebbe", quindi la
cosa e' molto differente da quello che chiedava il nostro "amico".
Inoltre quando dici "precalcolata" intendi dire che deve esistere una
funzione che "calcoli" quindi .... tale funzione prima o poi va fatta ;-)
Per finire e' un immenso spreco di memoria (non tanto per i char, ma anche
per quelli non ha assolutamente scopo questa cosa).
In sostanza il punto 3 credo sia stato messo solo per il "non c'e' 2 senza
3" ;-)
(battutaccia!)
Alex

risposta" il tutto richiede piu' tempo ancora....
L'uso delle tabelle di valori precalcolati (seno e coseno nei
programmi di grafica, per esempio) aumenta moltissimo le
prestazioni.  La funzione non calcola ogni volta che deve
utilizzare un valore (altrimenti non sarebbero valori
precalcolati).
--
CyberWalkie - walkietalkie(at)
libero.it

 >risposta" il tutto richiede piu' tempo ancora....
Ho detto ad ogni posizione dell'array, non ad ogni chiamata di funzione,
credo che tu abbia letto male.
Inoltre se leggevi oltre, proprio di seguito, strano che tu non l'abbia
notato:
<QUOTE>
(a meno che il programma non resti attivo per giorni a chiamare sempre la
stessa funzione... ma pure in questo caso non mi sembra assolutamente una
buona soluzione.)
</QUOTE>
E' chiaro che con questa frase intendevo che essendo i valori (pre)calcolati
solo una volta all'inizio, il costo di precalcolarli verrebbe distribuito
bene solo nel caso in cui "il programma resti attivo per giorni a chiamare
sempre la stessa funzione" !
Era ovviamente un esempio esagerato, per fare capire come la pensavo, ma
credo che fosse perfettamente chiaro che avessi compreso che i valori non
dovevano essere ricalcolati ad ogni chiamata di funzione.
Atrimenti, scusa, se venissero ricalcolati ad ogni chiamata di funzione
tutti i valori possibili per un int invece di calcolare solo il numero
desiderato bisognerebbe calcolarne 2^32 ogni volta ?!? C'e' una bella
differenza ;-) Invece di 1 ne calcoliamo 4294967296 ?!?
No, non intendevo questo e mi meraviglia che tu mi abbia fatto cosi' scemo
!!!
Alex

sempre la stessa funzione" !
Precalcolare dei valori come quelli che Sergio cita richiede un
tempo brevissimo (meno di mezzo secondo sulla mia macchina).
--
CyberWalkie - walkietalkie(at)
libero.it

 >sempre la stessa funzione" !
e' invece verissimo !!!
Ad esempio, se si usa un PC esclusivamente a questo scopo, ed una volta
precalcolati i valori (int a 32 bits ad esempio) il computer dovesse
ripetitivamente chiamare la funzione "per giorni" una chiamata dietro
l'altra, allora e' possibile che questa cosa sia valutabile, visto il largo
uso di tale funzione (anche se ....).
Ora questo e' un esempio assurdo, tanto piu' che una macchina 32 bits non
puo' indirizzare 17.179.869.184 bytes di memoria se non con l'uso di
particolari accorgimenti.
Non mi dire che pensavi che io parlassi di valori 8/16 bits in quanto ho
sempre e solo fatto riferimento a valori 32 bits (dove 32 e' solo un esempio
per un qualsiasi valore, anche 64/128 bits etc...)
Nel primo messagio in risposta a Sergio scrissi anche:
<QUOTE>
Per finire e' un immenso spreco di memoria (non tanto per i char, ma anche
per quelli non ha assolutamente scopo questa cosa).
</QUOTE>
Non e' vero anche questo, se anche fosse possibile, allocare
147.573.952.589.676.412.928 bytes per questa cosa, non e' uno spreco ?!?
(Nota che esplicitamente escludevo i char ed implicitamente i short)
In conclusione precalcolare dei valori e' a volte utilissimo, ma non in
questo!
Alex
P.S. ho la vaga sensazione che se io avessi scritto quello che ha scritto
Sergio tu avresti risposto piu' o meno come ho risposto io e mi avresti
attaccato... ;-)

questo!
Non so come fai a essere sicuro di questo ... ora provo con
il precalcolo su 256 valori e poi ti so dire...
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

ristretto il campo ai char o agli short !!!
Certo che si', Kirys riporta il caso di semplici 8 bit.
--
CyberWalkie - walkietalkie(at)
libero.it

 operazione cosi' poco costosa, cosi' poco che 2^32 numeri non causano
Nel mio post avevo, non a caso, parlato di char e "volendo" di  short.
In tali casi le dimensioni sono tollerabili, a fronte di un tempo di
risposta irraggiungibile con altri metodi (il costo computazionale in
esercizio è ovviamente la sola indicizzazione del vettore e tale semplicità
elimina inoltre l' eventuale overhead della chiamata ad una funzione
garantendo un soluzione "inline") . E' una tecnica che si giustifica in casi
in cui la velocità di risposta è il fattore critico (Oltre che nei programmi
di grafica tale soluzione può essere utilizzata ad esempio per controlli di
parità o in algoritmi di correzione di errore in sistemi di
telecomunicazione o nel controllo elettronico di motori a combustione). Per
generale intendevo che è applicabile per ogni funzione f (n) quale che sia
la sua complessità. Il tempo di inizializzazione per array di queste
dimensioni è solitamente trascurabile a fronte del tempo di caricamento ed
inizializzazione di un programma e comunque è una operazione una tantum che
si paga poi in termini di prestazioni (se servono).
Sarebbe come dire che vado da Milano a Londra in bicicletta perche' non
voglio perdere un ora a fare il controllo di imbarco in aeroporto.
----
Sergio Bianchi

 CyberWalkie - walkietalkie(at)
libero.it
In ogni caso se vogliamo parlare di 32 bit con una modesta table da 256 char
typedef ... union  {
   int n;
   char c[4];
   char s[2];
} x;
v.n = numero a 32 bit;
int numero di bits = table[x.c[0]] + table[x.c[1]] + table[x.c[2]] +
table[x.c[3]] ;
che non mi sembra male in termini di prestazioni per non parlare di una
table di short (1 addizione e due indicizzazioni)
se trovate qualcosa di meglio ....
int numero di bits = table[x.s[0]] + table[x.s[1]] ;
----
Sergio Bianchi

s nella union è ovviamente uno short.
----
Sergio Bianchi

 e a cosa servirebbe ?
dopo l'incremento di i, serve a controllare che il numero di 1 sia 
maggiore degli 0 (meta' + 1 del sizeof = maggioranza assoluta)

questo!
Dalle prove che ho fatto sul mio PIII/500 con BCC55 (ho anche
controllato che il codice assembler generato non contenesse
assurdita') ho ottenuto i seguenti dati:
  versione "n &= n-1"     9.40 sec
  versione tab8           1.88 sec
  versione tab16          1.65 sec
tab8 usa una tabella precalcolata di 256 byte
tab16 usa una tabella precalcolata di 65536 byte
Il tempo indicato e' quello impiegato per eseguire dieci milioni
di volte 5 conteggi di uno stesso valore pseudocasuale unsigned
a 32 bit...
  kw=6502; tot=0;
  t=clock();
  for (i=0; i<10000000; i++)
  {
    kw*=69069;
    tot+=bitcount(kw);
    tot+=bitcount(kw);
    tot+=bitcount(kw);
    tot+=bitcount(kw);
    tot+=bitcount(kw);
  }
  t=clock()-t;
Visti questi risultati personalmente credo che la versione
preferibile sulla mia macchina sia la tab8... come tempi e'
molto vicina a tab16 ma usa molta meno memoria (non sono un
problema solo i 64k ma il fatto che sono dati che rischiano
di invalidare una buona parte della cache interna del
processore: se nel programma vengono fatte altre
elaborazioni temporalmente contigue la routine tab16 ha
una buona probabilita' di risultarne rallentata e di
rallentarle.
I risultati sarebbero ancora piu' eclatanti in favore dell'uso
di tabelle se invece di contare il numero di bit a 1 di una
singola dword venisse richiesto di contare i bit a 1 di una
intera zona di memoria. In questa funzione infatti l'overhead
di chiamata non e' affatto trascurabile.


 ha

Grazie, questo lo avevo intuito, ma sizeof(n) restituisce (su macchine 32
bits) 4 e non 32. Restiuisce il numero di bytes e non di bits. Per questo
chiedevo una applicazione pratica.
Alex

 il precalcolo su 256 valori e poi ti so dire...
Ok, fallo sara' interessante, ma...
Chiedo a te ed ad Andrea Laforgia: Chi ha mai parlato di numeri 8 bits se
non chi ha tirato fuori questo metodo !?! La domanda era piu' generale !
Alex

 Certo che si', Kirys riporta il caso di semplici 8 bit.
Sarei curioso di vedere se si accontenta VERAMENTE di un metodo per
calcolare SOLO i bits ad 1 di variabili ad 8 bits.
Alex

 voglio perdere un ora a fare il controllo di imbarco in aeroporto.
Mi sta bene, infatti dicevo solo che la tua soluzione non andava bene in
quanto non e' generale visto che per interi a 32 bits non va, ad esempio,
bene !
Alex

   versione tab16          1.65 sec
Ovviamente e' piu' veloce, ma non e' generale.
Avevo detto che nel caso in cui si fosse sfruttato molto la funzione
allora...e tu l'hai sfruttata molto ;-)
Se per tab8 mi pare accettabile, per tab16 davvero non mi piace.
Per finire se invece vogliamo parlare di numeri in generali:
quindi 8-16-32-64-.... allora spero che tu sia concorde con quello che dico
da parecchi messaggi...
Il tuo test e' interessante, ma piu' o meno mi aspettavo risultati del
genere.
Sugli 8 bits mi sta bene, nel caso in cui si frutti parecchio la cosa, ma
oltre no !
(nonostante i tempi dei 16 bits).
Hai provato con 32 ;-) ?
Alex

 non chi ha tirato fuori questo metodo !?! La domanda era piu' generale !
E' vero quello che dite: nel messaggio principale era riportato un esempio
per 8 bits. Tuttavia credo fosse solo un esempio-prova, credo quindi che
stia cercando una soluzione generale e non una che va bene solo per numeri 8
bits.
Alex

 In ogni caso se vogliamo parlare di 32 bit con una modesta table da 256
char
I valori a 32 bits sono 2^32 e non 256 !!!
Alex

per quelli non ha assolutamente scopo questa cosa).
se si vuole ottimizzare in questo modo si possono seguire due strade:
o si fa una funzione che ricalcola tutti i valori ad ogni esecuzione
del programma oppure si fa del "preprocessing": ovvero, ti calcoli
quei valori una volta per tutte e li metti come costanti nel tuo
programma.
Inoltre l'algoritmo di preelaborazione (sia a run-time che a
(pseudo)compile-time) si presta bene ad ulteriori ottimizzazioni: mi
sembrerebbe un buon esempio di programmazione dinamica.
Anto
--
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

"Alex" ha scritto:
emmm
opss....
manca un *8 
:)

Hai provato con 32 ;-) ?
Pensavo fosse ovvio... in tutti i casi io calcolavo il numero
di bit a 1 di un numero unsigned a 32 bit. Con la tabella a 8
sono 4 lookup, con la tabella a 16 sono due lookup.


"Alex" <nom...@bow.wow> ha scritto nel messaggio
news:BiX17.11588$eB4.4...@news.infostrada.it...

Ho effettuato la segmentazione della variabile tramite una union.
I valori a 32 bits sono composti da 4 byte. Nel caso specifico siccome
stiamo contando i bits, il totale di essi è la somma dei totali delle
sottoparti. Per questo è lecito utilizzare una tabella a 256 valori per ogni
byte componente la variabile a 32 o maggiore come ha giustamente fatto
notare Andrea Griffini parlando di un generico blocco di memoria.
----
Sergio Bianchi

 I valori a 32 bits sono 2^32 e non 256 !!!
Scusa !
Non avevo capito cosa intendevi, hai ragione, e' possibile fare come dici.
Scusa ancora se non ho capito quello che intendevi...
Alex

 sono 4 lookup, con la tabella a 16 sono due lookup.
Spezzando l'int32 in 4bytes e sommando i risultati ... emh...
Beh, questo non e' del tutto male...
Alex
P.S. strano che non mi sia venuto in mente, beh, amen a volte capita...
Hai ragione cmq era ovvio ed avrei dovuto arrivarci !

 notare Andrea Griffini parlando di un generico blocco di memoria.
Si, noto questa risposta dopo aver appena risposto a me stesso...
Me ne sono accorto e chiedo scusa per non aver capito...
(le nostre due risposte sono state spedite nello stesso momento, in questo
modo io non ho visto la tua e tu non hai visto la mia ;-)
Alex


Nessun problema, alla prossima
Ciao.
----
Sergio Bianchi