Newsgroup: it.hobby.elettronica.digitale
Titolo: Calcolare la parità di un byte in C

Ciao a tutti,
dovrei contare tutti i bit = 1 all'interno di un byte.
Ad esempio,se il mio byte pippo è 11100000 in binario,la somma di tutti 
gli 1 è 3.
Senza dover puntare ai singoli bit con un contatore so che si puo' fare 
con degli shift,ma non so' come.
Grazie
Spectre

Spectre ha scritto:

Ho trovato questa strada e sembra andare bene.Mi chiedo se è la versione 
più compatta possibile.
int bits(unsigned i) {
int n = 0;
while (i) {
i &= i-1;
++n;
}
return n;
}
Saluti
Spectre


int numBit(unsigned char bits)
{
      int nBits=0;
      while(bits)
      {
          if(0 !=   ((bits= (bits>>1))&0x1)  )
            nBits++;
      }
      return(nBits);
}
int numBit(unsigned char bits)
{
      int nBits=0;
      while( bits )
      {
         nBits += (bits&0x1)
         bits = (bits >>1)
      }
      return(nBits);
}
B.

 ha scritto nel messaggio
news:48f464b6$0$14495$5fc...@news.tiscali.it...

per me questo che hai trovato è una figata,con al massimo 8 loops e in poche
righe ottiene lo scopo,non lo conoscevo


"blisca" <bliscachiocciolinatiscalipuntoit> ha scritto nel messaggio 
news:48f4edb3$0$40308$4faf...@reader5.news.tin.it...

Trovate questo ed altri metodi qua
http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
Ciao
Pow 

 dovrei contare tutti i bit = 1 all'interno di un byte.
ma devi calcolare la parita' oppure contare gli uni ?
deve essere per forza in C ?
la parita' in asm puo' essere + compatta, dipende dal set di istruzioni.
saluti

 ma devi calcolare la parita' oppure contare gli uni ?
E' la stessa cosa!
-- 
Resistance is useless!  (If < 1 ohm)
News 2002 [v 2.1] / StopDialer / PopDuster - 
http://www.socket2000.com
Akapulce portal: 
http://www.akapulce.net

 con degli shift,ma non so' come.
Al di là di tutti i possibili algoritmi, il metodo più veloce e più
semplice è quello di testare l'apposito flag di parità della CPU.
Sfortunatamente non tutte le CPU hanno questo flag e comunque
è accessibile solo da assembly.

 
certo, certo, hai ragione.
infatti la parita' di  11100000  e'  3 , vero ?

 infatti la parita' di  11100000  e'  3 , vero ?
Ehm... scusa, ma è evidente che non hai afferrato il concetto di 
"parità". Non si tratta di sapere se un dato byte è pari o dispari...
Forse su wikipedia puoi farti una piccola cultura:
http://it.wikipedia.org/wiki/Bit_di_parit%C3%A0
Per poter applicare quindi il calcolo della parità (pari o dispari) è
necessario CONTARE quanti 1 sono presenti nel byte.
-- 
IBM: Ill-mannered Besotten Macrocasm


 
mah, tu dici che e' necessario contare gli uni ?
forse perche' e' l' unico modo che conosci e che usi.
vuoi imparare qualcosa sulla parita' ?
e' un bit (1 oppure 0).
non e' il numero di uni (che nell' esempio dell' OP sono 3).
e la parita' (even) di  11100000  e'  1, non e' 3 !
se leggi bene sul tuo link di wikipedia:
.....
A vuole trasmettere:                     1001
A calcola il bit di parità:              1^0^0^1 = 0
.....
lo vedi ? non e' due, e' zero!
per calcolare la parita' non e' assolutamente necessario contare gli uni
perche' il risultato e' un solo unico piccolo bit, che si puo' calcolare
senza contatori (come si fa in hardware).
ti saluto.

 senza contatori (come si fa in hardware).
Certo. Lo si fa anche in altri modi, però magari non sono poi così 
performanti...
http://groups.google.com/group/comp.lang.c/msg/e65b8577d041435b?hl=en&
C'è di mezzo un'elevazione a potenza e cito:
"...If this code is critical for performance, as it is in some 
applications, I think the last three lines beginning with "x ="
should be replaced by the table lookup..."
-- 
A bug in the code is worth two in the documentation.


   
se ci sono problemi di prestazioni, una bella lookup table e' il
sistema piu' veloce, in alternativa una tabella compressa
a bit potrebbe essere un compromesso...
static
unsigned char TAB_PARITY[]={
    0x69, 0x96, 0x96, 0x69, 0x96, 0x69, 0x69, 0x96,
    0x96, 0x69, 0x69, 0x96, 0x69, 0x96, 0x96, 0x69,
    0x96, 0x69, 0x69, 0x96, 0x69, 0x96, 0x96, 0x69,
    0x69, 0x96, 0x96 ,0x69, 0x96, 0x69, 0x69, 0x96
};
char isParityEven(unsigned char p)
{
    return( TAB_PARITY[(p/8)]&(1<<(p%8)) );
}
Volendo evitare lo shift:
char isParityEven(unsigned char p)
{
    static
    unsigned char TAB_MASK[]={0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 
0x80};
    return( TAB_PARITY[(p/8)]&TAB_MASK[(p%8)]);
}
B.

 C'è di mezzo un'elevazione a potenza e cito:
Scusate se mi intrometto. Per curiosità, dove vedi l'elevazione a potenza?
Marco / iw2nzm

 Marco / iw2nzm
Hai ragione, è uno xor. Non cambia però lo stato delle cose. Alla 
fine che si adotti un metodo o un'altro sempre gli uno si contano...
-- 
Memory dump:  Amnesia...
News 2000 [v 2.06] - 
http://www.akapulce.net/socket2000

 fine che si adotti un metodo o un'altro sempre gli uno si contano...
Sinceramente non capisco perchè insisti a dire che
bisogna "contare" gli uno.
Non è necessario un contatore, basta un semplice flip
flop, a meno che tu non voglia dire che anche un flip flop
è un contatore a un bit, ma mi sembrerebbe una definizione
molto tirata.
In ogni caso la parità di un byte può essere calcolata anche
da una pura rete combinatoria e ti sfido a dire che tale
rete combinatoria esegua un conteggio!

 rete combinatoria esegua un conteggio!
Questo è un sommatore:
http://www.iismattei.it/cartelle_prof/CANCRO_34/DIGITALE/img/adder.gif
Come noterai è una rete combinatoria. Eppure fa le somme...
Sta di fatto che la parità è data dal numero di 1 presenti nel byte o
nella word da controllare. Contarli e prendere le relative decisioni 
è forse il metodo più semplice da realizzarsi via software. Altre 
soluzioni potrebbero essere più eleganti alla vista ma magari 
richiedere più tempo o più spazio. Quindi contare gli uno o calcolare
la parità, di fatto, indicano la stessa cosa.
-- 
I used to have a life, then I got v32bis!


 la parità, di fatto, indicano la stessa cosa.
Non sono d'accordo: la parità contiene meno informazioni rispetto al 
conteggio degli uno (un bit contro 3 per un byte o 4 per una word). Per 
cui se è vero che contare gli uno può servire a calcolare la parità non 
è vero il viceversa.
Quindi non si può affermare che, di fatto, indicano la stessa cosa.
Ciao!
Marco / iw2nzm

 Quindi non si può affermare che, di fatto, indicano la stessa cosa.
E' vero, ho dimenticato un dogma:
In un thread che si intitola: "Calcolare la parità di un byte" 
contare gli uno indica la stessa cosa.
-- 
AAAAAA - American Association Against Acronym Abuse Anonymous


 Quindi non si può affermare che, di fatto, indicano la stessa cosa.
Ho rinunciato da tempo ad interloquire col tipo. Quando si incaponisce (e
gli capita spesso) non c'è verso di farlo ragionare. Se messo alle strette
può anche diventare molto molto "antipatico".

 
ma citi a caso o sei un troll ?

 ebbe l'ardire di profferire:

Quando dimostrerai che contare gli uno non serve al calcolo della 
parità potrai aprire bocca. Il resto sono pippe mentali per chi crede
di sentirsi furbo perchè applica una rete combinatoria anzichè un 
algoritmo.
-- 
IBM: In Business (for) Money


 ma citi a caso o sei un troll ?
Ricapitoliamo perchè o non hai capito una cippa tu o non l'ho capita 
io. Propendo per la prima ma nessuno è infallibile. Il titolo: 
"calcolare la parità", il messaggio: devo contare gli uno.
Bene. Se a lui serve contare gli uno e leggersi 'ste risultato (per 
poi calcolarsi la parità) sono fatti suoi. Evidentemente ha qualche 
necessità che non conosciamo. Tu salti fuori dicendo che non è così 
che si calcola la parità. Bene. Diciamo pure che se avessi avuto meno
spocchia magari il thread sarebbe già concluso. Non vieni ad 
insegnare a me come si calcola la parità e quali siano i metodi, ma 
pare che tu ti sia sentito in dovere di pensare che io o altri 
dipendano dal tuo verbo (la battutina sul numero 3 degli uno è 
emblematica).
Libero di pensarla come vuoi, anche che sia sbagliato contare gli uno
per poi applicare la parità, non è che la cosa mi tanga poi più di 
tanto.
-- 
IBM: Insanely Better Marketing


 parità potrai aprire bocca.
contarli è uno dei modi, ma non è strettamente necessario per calcolare 
la parità

 Due di Picche ha scritto:

Ho scritto da qualche parte che è l'unico modo forse?
-- 
IBM: Incredibly Big Monster


 
rileggi quello che hai scritto

 rileggi quello che hai scritto
Rileggiti l'intero thread, magari lo capisci.
-- 
My mail reader can beat up your mail reader.


 
studiati la tabella di verità dell'implicazione logica (A=>B)( cfr 
http://it.wikipedia.org/wiki/Implicazione
 )  e rifletti su:
 > Ho scritto da qualche parte che è l'unico modo forse?
 > Quando dimostrerai che contare gli uno non serve al calcolo della 
parità potrai aprire bocca.

 parità potrai aprire bocca.
Vedo che NON HAI letto il thread. Ok, vuoi solo rompere le pelotas 
giusto per puntualizzare. Fai pure. Quel che c'era da dire è stato 
detto.
-- 
Hex dump:  Where witches put used curses...


 
il tuo problema non è (beh, almeno spero) capire un concetto così 
facile, ma ammettere una svista dopo aver fatto la ruota del pavone: in 
questi termini è inutile continuare, quindi non ti risponderò ancora.

Due di Picche ha scritto:
[cut]
si, ho letto, ho risposto ieri, il messaggio e' in viaggio e prima o
poi apparira'.


 > ebbe l'ardire di profferire:
 >
 >
 >> non hai ancora capito la differenza tra contare gli uni e calcolare 
la=20
 >> parita'.
 >
 > vengo ad impararla da te, maestro. ROTFL.
non puoi venire a imparare niente da me, perche' io non voglio
perdere tempo nel tentativo inutile di insegnarti qualcosa.
 >>> Eh grazie. Ma ti assicuro che SO BENE cosa sia.
 >> non credo proprio.
 >
 > Non è un problema mio.
le due cose sono completamente diverse, soprattutto nel formato del
risultato; se scrivi SW e non capisci la differenza, e' un problema tuo.
 >
 >> e secondo te contare gli uni sarebbe performante ?
 >> dal punto di vista del codice, della ram, dello stack, della 
velocita'o =
 >
 > Vedi tu. Lo stesso spectre s'è dato la soluzione
ma _tu_ non hai una risposta valida alla mia domanda qui sopra ?
 >
 > int bits(unsigned i) {
 > int n = 0;
 > while (i) {
 > i &= i-1;
 > ++n;
 > }
 > return n;
 > }
questo va benone _se_ deve contare gli uni.
IMHO la riga "i &= i-1" e' assemblata con 3 opcode store_dec_and :
usando shift_jpnc si lima un opcode.  poi il codice potrebbe essere
+ compatto con do_while perche' testa il flag Z dopo lo shift invece
che a inizio ciclo e quindi si lima via il jmp a fine ciclo;
volendo invece calcolare la parita' si puo' fare ancora meglio.
 >
 >> ma citi a caso o sei un troll ?
 >
 > Ricapitoliamo perchè o non hai capito una cippa tu o non l'ho capita
 > io. Propendo per la prima ma nessuno è infallibile. Il titolo:
 > "calcolare la parità", il messaggio: devo contare gli uno.
e qui io, cogliendo la differenza, ho chiesto educatamente "quale delle
due" , mentre tu dici che sono la stessa cosa.
 > Bene. Se a lui serve contare gli uno e leggersi 'ste risultato (per
 > poi calcolarsi la parità) sono fatti suoi.
qui stai immaginando intensamente oppure conosci i fatti suoi ?
 > Evidentemente ha qualche necessità che non conosciamo.
e' piu' che evidente che non la conosci, ma fai ancora peggio: l' OP ha
scritto che
"Senza dover puntare ai singoli bit con un contatore so che si puo' fare
con degli shift,ma non so' come."
e nonostante questa dichiarazione tu insisti col contatore.
 > ...Tu salti fuori dicendo che non è così che si calcola la parità.
falso.
io ho scritto che:
la parita' in asm puo' essere + compatta, dipende dal set di istruzioni.
e' un bit (1 oppure 0).
non e' il numero di uni (che nell' esempio dell' OP sono 3).
e la parita' (even) di  11100000  e'  1, non e' 3 !
per calcolare la parita' non e' assolutamente necessario contare gli uni
perche' il risultato e' un solo unico piccolo bit, che si puo' calcolare
senza contatori (come si fa in hardware).
confermo tutto e aggiungo che:
IMHO,  tra tutti i modi possibili, contare gli uni e' il peggiore.
ma sono pronto a valutare Vs smentite e Vs esempi funzionanti.
 > Bene. Diciamo pure che se avessi avuto meno
 > spocchia magari il thread sarebbe già concluso.
ti ringrazio dell' ottima idea: chiunque puo' leggere i miei ed i tuoi
post e decidere da che parte stanno falso e spocchia.
 > Non vieni ad
 > insegnare a me come si calcola la parità e quali siano i metodi,
io non indico metodi prima di aver capito la richiesta dell' OP;
tu hai citato, confondendo XOR con elevamento a potenza, un esempio in
cui:
  1) con shift+exor+and accumula in 1 bit la parita' di 2 bit.
     (ma non conta gli uni)
  2) con shift+exor+and accumula in 1 bit la parita' di 16 bit.
     (ma non conta gli uni)
  3) con accesso a tabella preleva direttamente il risultato.
     (ma non conta gli uni)
ecco quindi che ti ho chiesto:  ma citi a caso o sei un troll ?
 > ma
 > pare che tu ti sia sentito in dovere di pensare che io o altri
 > dipendano dal tuo verbo (la battutina sul numero 3 degli uno è
 > emblematica).
non era una battutina: ho riciclato il "byte pippo" dell OP Spectre che
"è 11100000 in binario,la somma di tutti gli 1 è 3"
per farti notare che la parita' (1) e' diversa dal numero di uni (3).
 > Libero di pensarla come vuoi, anche che sia sbagliato contare gli uno
 > per poi applicare la parità, non è che la cosa mi tanga poi più di
 > tanto.
 >
eh certo, l' uva era acerba e perdere tempo cosi' e' un vero peccato.
saluti (ultimi)


-- 
User: A harmless drudge.
