Newsgroup: it.comp.lang.c
Titolo: mappa di 128 bit

mi ritrovo con un array come questo:
long int maschera[32];   (una printf di sizeof(long int), mi da 4)
e se so ancora fare le moltiplicazione penso sia di un totale di 128 bit :)
La mia domanda e' la seguente, c'e' un modo per ottenere il numero 
totale degli elementi posti a 1 ? e c'e' un modo per poter estrapolare 
quali posizioni sono poste a 1 ?
Grazie infinite.
Ciao
	MaX

 e se so ancora fare le moltiplicazione penso sia di un totale di 128 bit :)
i 128 sono Byte, non bit, quindi mi ritrovo con una "mappa" di 1024bit.
scusate la distrazione, puo' capitare :P
la domanda rimane sempre la stessa:


 e c'e' un modo per poter estrapolare quali posizioni sono poste a 1 ?
questo lo puoi memorizzare in un vettore, segnandole come coordinate...
 

> quali posizioni sono poste a 1 ?
qualcosa tipo:
    long int maschera[32];
    int pos=0, tot=0;
    long int i,j;
    for(i=0;i<32;i++) {
       for (j=0;j<sizeof(long int)*8;j++)
          if (maschera[i] & (1<<j)) {
             ++tot;
             pos=(i*8)+j;
          }
    }
tot ti da il totale dei bit a 1, pos è la posizione (da 0 a 
1023) che ti devi giostrare tu di volta in volta asegandola 
per esempio a un posto progressivo in un array.
ciao.

             pos=(i*8)+j;
scusa volevo dire:
pos=(i*sizeof(long int)*8)+j;
ciao.

    }
sulla mia maschera esegue 1024 iterazioni per mostrare il risultato corretto 
(55). Infatti 32 * (4*8) = 1024.L'if viene quindi valutato 1024 volte.
Il mio algoritmo:
for(i=0; i<32; ++i)
{
   tmp = maschera[i];
   while(tmp){
      tmp &= tmp-1;
      ++count;
   }
}
sulla stessa maschera esegue 55 iterazioni. Infatti il ciclo esterno cicla 
32 volte e quello interno cicla tante volte quante sono i bits ad uno 
nell'intero che viene analizzato. Quindi se tutti e 32 i long sono settati a 
0 avremo solo 32 iterazioni esterne e 0 interne (32*0). Nel caso pessimo in 
cui tutti i numeri siano settati a -1 (32 bits a uno) allora avremo 32 
iterazioni esterne e 32*32 = 1024 iterazioni interne (come nel tuo caso). 
Nel caso specifico invece abbiamo solo 32 iterazioni esterne e 55 interne.
Insomma usare "n &= n-1" per contare i bits ad uno e' molto piu' efficiente 
che controllare ogni singolo bit alla volta.
HTH,
Tommaso

 che controllare ogni singolo bit alla volta.
In effetti e' molto "fine", ma non riesco a trovare il modo per 
determinare i valori n-esimi sui quali il bit e' posto a 1.
cioe' se 001101.....
il primo 1 e' in TERZA poszione
il secondo 1 in QUARTA
il terzo 1  in SESTA
......
Grazie a tutti per l'aiuto e i suggerimenti
Ciao
	MaX

 [ ... ]

YattaMaX wrote:
A latere, ti consiglio di usare non dei long int,
ma degli unsigned long int.
Il fatto che un bit sia di segno complica inutilmente le cose:
quando si lavora a livello bit e' molto meglio usare tipi
di dato unsigned.
ciao,
g.


certo, in effetti hai ragione, ma quella e' una "mappa di bit" che non 
posso decidere io, quindi la devo tenere cosi' (in poche parole e' una 
variabile fd_set).
Grazie comunque per il consiglio.
Ciao
	MaX

 }
Questo algoritmo è efficiente quando la word è scarsamente popolata.
La versione duale (efficiente con word altamente popolate) è la seguente:
count = 32;
while (tmp != -1)
{
   count--;
   tmp |= tmp+1;
}
Praticamente conta gli zeri...
Oppure si può evitare il while:
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x3F;
Ecc...
Kiuhnm


Ma per ottenere il valore della posizione di ogni bit trovato ad 1 ?
cioe':
00001001000
Partendo da sinistra:
-> 5
-> 8
Grazie.
Ciao
	MaX

 -> 8
Si tratta di calcolare il log_2(x).
Non esiste un modo efficiente se non usare gli opcode della CPU (per es. 
  BT, BTC, BTR, BTS, ecc...) o due look-up table.
Kiuhnm