Newsgroup: it.comp.java
Titolo: bit di parita'

Ciao a tutti,
ho bisogno di sapere se un intero, nella sua rappresentazione binaria, ha un
numero pari di 1. Avrei giurato che c'è un metodo da qualche parte o un
qualche trucchetto con gli operatori ma non ho trovato niente.
Pare proprio che bisogna per forza iterare sui bit.
Allora quello che ho scritto è questo:
int par = 0;
for(int t = <numero da analizzare>; t >0; t >>>= 1) 
  par = (t & 1) ^ par;
 
e se par == 0 il numero di 1 è pari. Qualcuno conosce un metodo più veloce?
Grazie
Matteo
-- 
chi sono e soprattutto chi non sono:
http://www.ilnomedeldominio.it
un piccolo programma per studenti universitari:
http://inutility.ilnomedeldominio.it/imsv/




Scusa ma l'unico numero in cui tutti i bit sono a zero è lo zero. per qualunque altro numero almeno un bit ==1.



....sono perplesso....forse ho frainteso il problema

Ciao











-- 
.....................................................................
vieni a trovarmi ......
http://www.glz.it
 
dai vita al tuo sito .....
http://www.talkwithus.it

.....................................................................












 ....sono perplesso....forse ho frainteso il problema
Ho bisogno di sapere se il numero di bit a 1 in un dato intero è pari o
dispari. Certo, un numero != 0 ha almeno un bit a 1, ma io voglio sapere
quanti :) Anzi mi basta sapere se sono un numero pari per questo nel ciclo
non li conto ma faccio lo xor. xor di un numero pari di uno vale 0 mentre
di un numero dispari vale 1.
Ciao


 di un numero dispari vale 1.
Quelli che tu cerchi sono gli "evil" e "odious numbers":
http://www.tanyakhovanova.com/Numbers/numbers.html#evil
http://www.tanyakhovanova.com/Numbers/numbers.html#odious
Piu' informazioni su
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001969
Mia personalissima soluzione al problema:
0) Risultato = 1
1) Risultato = Ultimo bit del numero XOR Risultato
2) Shift del numero verso destra
3) Ritorna a 1) finche' shiftato tutto il numero
Se alla fine Risultato == 1, allora il nr. di bit e' pari.
O, meglio, scegli in 0) il valore di Risultato come vuoi e controlla se
alla fine del ciclo e' il valore e' cambiato.
Non so quanto sia efficente, ma e' facilmente implementabile in un
linguaggio di basso livello :)
-- 
Giambo - Occhio al filtro antispam _e_ alla whitelist !

 3) Ritorna a 1) finche' shiftato tutto il numero
Tornando alla radice di questo thread è quello che avevo scritto, con la
differenza che vado avanti finché numero != 0 (avevo scritto >, devo
correggere) perché tanto se è == 0 non ci sono più bit a 1.
Cmq anche tu dici che non c'é modo di evitare l'iterazione sui bit?
Grazie


 ....sono perplesso....forse ho frainteso il problema
La domanda era un altra:
"ho bisogno di sapere se un intero, nella sua rappresentazione binaria, ha  
un
numero pari di 1"
-- 
Manny Calavera
AntiSpam: CAVA²
Using Opera's revolutionary e-mail client: 
http://www.opera.com/mail/

 Cmq anche tu dici che non c'é modo di evitare l'iterazione sui bit?
Non credo proprio. Puoi controllare che il numero sia uguale a tutti i
numeri della serie (3, 5, 6, 9, ...), ma non credo sia molto efficente :-)
Inoltre mi sembra strano che tu possa sapere il numero di bit uguali a 1
all'interno di una serie senza doverli contare (E quindi interare su
tutti i bit).


 e se par == 0 il numero di 1 è pari. Qualcuno conosce un metodo più veloce?
Ciao Matteo,
l'unica cosa che mi viene in mente è dimiuire il numero di iterazioni 
usando una lookup table. Ho fatto un esempietto; mi sembrava più 
semplice che spiegarlo a parole :)
Controllando un byte alla volta, invece di un bit, sul mio pc ci mette 
circa 1/4 del tempo.
without lookup table: 797ms
with lookup table: 203ms
<CODE>
public class TestLookupTable {
     private final int[] evenLookupTable = new int[256];
     public TestLookupTable() {
         for (int i = 0; i < 256; i++) {
             evenLookupTable[i] = isEven(i);
         }
     }
     public int isEven(int number) {
         int par = 0;
         for (int t = number; t != 0; t >>>= 1) {
             par = (t & 1) ^ par;
         }
          return par;
     }
     public int isEvenWithLookup(int number) {
         int par = 0;
         for (int t = number; t != 0; t >>>= 8) {
             par = evenLookupTable[t & 0xFF] ^ par;
         }
         return par;
     }
     public static void main(String[] args) {
         TestLookupTable lookupTable = new TestLookupTable();
         long start = System.currentTimeMillis();
         for (int i = 0; i < 10000000; i++) {
             lookupTable.isEven(i);
         }
         System.out.println("without lookup table: " + 
(System.currentTimeMillis() - start) + "ms");
         start = System.currentTimeMillis();
         for (int i = 0; i < 10000000; i++) {
             lookupTable.isEvenWithLookup(i);
         }
         System.out.println("with lookup table: " + 
(System.currentTimeMillis() - start) + "ms");
     }
}
</CODE>
Marco
-- 
reply: remove duh.spam.
http://cthulhu.zapto.org

 usando una lookup table. 
Uhmmm buona idea! Magari invece di un array di int potrei usare un BitSet
così dovrebbe usare solo 64 byte.
Ok, grazie :)
Ciao
