[c]giocando con i bit...

[NA01]

ho una serie imprecisata di numeri interi, devo sapere quante volte la sua versione binaria passa fa 0 a 1 e viceversa...
la coa più intelligente che ho al momento è un coso che tratta la sequenza come stringhe e le va a contare in modo stupidissimo...
esiste qualche modo intelligente per farlo?

ciao ciao!!! :-)

[trallallero]

Originariamente inviato da NA01

ho una serie imprecisata di numeri interi, devo sapere quante volte la sua versione binaria passa fa 0 a 1 e viceversa...
la coa più intelligente che ho al momento è un coso che tratta la sequenza come stringhe e le va a contare in modo stupidissimo...
esiste qualche modo intelligente per farlo?

ciao ciao!!! :-)

cosa intendi per versione binaria ?
comunque esiste l´operatore << o >> che shifta i bit di n posizioni verso destra o sinistra. Se ti puo´ servire

[Furla]

shifta e maschera, evita di sprecare spazio trasformandoli in stringa o in altro tipo.

[cionci]

Concordo: ti fai una copia dell'intero...poi testi il primo bit se è a zero o 1 con un & con 0x0001. A questo punto fai uno shift a destra e riparti da capo.

[NA01]

si, così mi evito la conversione, ma non ha molta importanza la velocità in questo caso (dato che comunque sarei costretto a farlo prima dell'esecuzione del programma).
quindi mi state confermando che non esistono modi intelligenti per capirlo al volo senza operazioni complesse (tenendo conto che deve giarere su un sistema che deve processare dati in tempo reale che già ora sta soffrendo un pò i troppi calcoli).
grazie, ciao!

[cionci]

Mmmmhhh...non so sinceramente quale sia la versione più semplice fra il convertire in stringa e l'usare & e shift che sono comunque operazioni semplicissime per la CPU.

In alternativa ti propongo un metodo carino...e quasi immediato. Considera però che devi avere 512 byte di memoria disponbile.

typedef struct XCHANGE 
{
  unsigned char x01;
  unsigned char x10;
} XCHANGE;

XCHANGE table[256];

table[0].x01 = 0;
table[0].x10 = 0;
table[1].x01 = 0;
table[1].x10 = 1;
table[2].x01 = 1;
table[2].x10 = 1;
table[3].x01 = 0;
table[3].x10 = 1;
table[4].x01 = 1;
table[4].x10 = 1;
table[5].x01 = 1;
table[5].x10 = 2;
table[6].x01 = 2;
table[6].x10 = 2;

e così via fino a 256. Nota che questa operazione ha costo zero al momento del controllo perché la andrai a farei solamente una volta durante tutta l'esecuzione del programma.

A questo punto la prima parte da controllare sarà questa:

int data = XXXXXX;

unsigned char dataByte1 = (unsigned char)(data & 0xFF);
unsigned char dataByte2 = (unsigned char)((data & 0xFF00) >> 8);
unsigned char dataByte3 = (unsigned char)((data & 0xFF0000) >> 16);
unsigned char dataByte4 = (unsigned char)((data & 0xFF000000) >> 24);

int x01 = table[dataByte1].x01 + table[dataByte2].x01 + 
             table[dataByte3].x01 + table[dataByte4].x01;

int x10 = table[dataByte1].x10 + table[dataByte2].x10 + 
             table[dataByte3].x10 + table[dataByte4].x10;

Non è finita perché mancano ancora gli scambi fra 01 e 10 fra i vari byte, questa è ancora più semplice e immediata:

unsigned int sideBit1 = data & 0x01800000;
unsigned int sideBit2 = data & 0x00018000;
unsigned int sideBit3 = data & 0x00000180;

if(sideBit1 == 0x1000000) x01++;
if(sideBit1 == 0x0800000) x10++;
if(sideBit2 == 0x10000) x01++;
if(sideBit2 == 0x08000) x10++;
if(sideBit3 == 0x100) x01++;
if(sideBit3 == 0x080) x10++;

[71104]

io propenderei per lo shift: è vantaggioso rispetto alla soluzione di cionci perché ti risparmi i 512 bytes di memoria, ed è vantaggioso rispetto alla conversione a stringa perché la conversione a stringa richiede sicuramente un numero maggiore di operazioni. ma ci vuole tanto a fare uno shift e controllare il bit meno significativo?

verrebbe così:

int nTestValue;
.
.
.

unsigned int uBitCount = sizeof(nTestValue) * 8;  // notare le manie di portabilità estrema :asd:

for (int i = 0; i < uBitCount; i++) {
	if ((nTestValue >> (i + 1)) & 1) {
		// ho trovato un 1
	}
	else {
		// ho trovato uno zero
	}
}

edit - ho modificato leggermente il programma affinché il test non modifichi il valore della variabile nTestValue.

[cionci]

Originariamente inviato da 71104

ma ci vuole tanto a fare uno shift e controllare il bit meno significativo?

E' quello che gli avevo proposto io all'inizio, ma se mi ha detto che è troppo costoso in termini di performance sicuramente la mia soluzione è meno costosa in termini di calcolo, ma più costosa dal punto di vista della memoria.

PS: avevo fatto qualche errorino sopra...corretto

[W.S.]

più leggero e performante dello shift credo ci sia solo asm in-line...
Io voto per lo shift

[cionci]

Per farlo più leggero dell'algoritmo di 71104 c'è c'è la possibilità di giocare con i bit per il conteggio per evitare l'if.
Da notare che non vuole contare il numero di 1 e di 0, ma il numero di passaggi da 1 a 0 e da 0 a 1.

Ecco qui:

/*in counter[0] ci sono i passaggi da 1 a 0, in counter[1] i passaggi da 0 a 1 */
int counter[2]: 

int data = xxxxx;
unsigned char previousLsb = data & 1;

data >>= 1;

for (int i = 1; i < uBitCount; i++) 
{
    unsigned char lsb = data & 1;
    data >>= 1;
    counter[lsb] += lsb ^ previousLsb;
    previousLsb = lsb;
}

Poi si potrebbe anche lavorare di loop unrolling....e sviluppare tutto il loop.

[cionci]

Correzioncina sopra