[C/C++] Operazioni su una stringa di bits...

[Tommo]

Salve,
volevo accompagnare la tesina (si sono in ritardo bestia :D ) con una simpatica demo, dato che tutti portano powerpoint e io non mi sentivo da meno :D

Cmq apparte ciò, ho sviluppato un programmino bastanza semplice che simula l'evoluzione di "bestie", che vengono generate proceduralmente a partire da una stringa di bits, la quale viene modificata per delezione o modifica o crossover secondo lo standard degli algoritmi genetici.

Solo che qui mi perdo: come fare per modificare UN bit per volta, oppure per toglierne uno e far scorrere tutti gli altri, su un array lungo N?
Sono completamente a digiuno di operazioni bitwise :doh:

Avevo anche pensato di usare una sequenza di char con valori fra 0 e 3, come in natura, ma poi non saprei come creare un numero decimale partendo da base 4...

Grazie per l'aiuto! :D

EDIT: Prego un moderatore qualsiasi di aggiungere la tag [C/C++], poichè l'ho dimenticata... :doh: :muro:

[DanieleC88]

Uhm, temo che i moderatori ti chiuderanno il thread... :D

Non hai specificato il linguaggio che usi, né ho capito bene cosa intendi fare di preciso: se devi prelevare un solo bit alla volta, un qualsiasi intero è sufficiente, potrai estrarre l'ultimo bit con (numero & 1) e farlo scorrere verso destra (uno shift che ti elimina l'ultimo bit) con numero >>= 1 (il tutto, nella sintassi del C, poi dipende dal tuo linguaggio).

[Tommo]

Eh lo so mi sono scordato la tag e l'ho ricordata quando era troppo tardi... :doh:

Il linguaggio è C++, quindi C va benissimo.

Mettiamo che io ho una sequenza
10001011 01010110 11010101

Voglio poter invertire un bit a caso, trovando la posizione con random().

E mi serve anche poter togliere un bit da una posizione qualsiasi, ed aggiungerne uno alla fine.

10001011 01X101101 10101011

Cosìcchè quando lo vado a leggere come char i valori sballano.

[DanieleC88]

Be', se ti serve di leggere il bit di indice 31 (il 32-simo), puoi usare (1 << 31), che ti darà:
10000000000000000000000000000000

Con un semplice AND sul valore originario potrai filtrare il solo bit che ti interessa. Puoi anche farti delle macro:
#define BIT(i) (1 << (i))
#define BIT_TEST(n, i) (((n) & BIT(i)) >> (i))

Una volta trovato il numero che attivi il singolo bit di indice i (con la macro BIT), è banale disattivare quel singolo bit:
inline void clear_bit(int *n, int i)
{
int mask = BIT(i);
int result = (*n);

result &= (~mask);
(*n) = result;
}

Et cetera... con poco sforzo dovresti riuscire a fare tutto. Solo non mi è chiara una cosa: intendi anche fare uno scorrimento, dove isoli un singolo bit di indice n dal numero e lo "trasporti" in una nuova posizione m nel numero? Oppure intendevi solo disattivarne uno (clear_bit()) e impostarne un'altro?

[Tommo]

Be', se ti serve di leggere il bit di indice 31 (il 32-simo), puoi usare (1 << 31), che ti darà:
10000000000000000000000000000000

Con un semplice AND sul valore originario potrai filtrare il solo bit che ti interessa. Puoi anche farti delle macro:
#define BIT(i) (1 << (i))
#define BIT_TEST(n, i) (((n) & BIT(i)) >> (i))

Una volta trovato il numero che attivi il singolo bit di indice i (con la macro BIT), è banale disattivare quel singolo bit:
inline void clear_bit(int *n, int i)
{
int mask = BIT(i);
int result = (*n);

result &= (~mask);
(*n) = result;
}

Et cetera... con poco sforzo dovresti riuscire a fare tutto. Solo non mi è chiara una cosa: intendi anche fare uno scorrimento, dove isoli un singolo bit di indice n dal numero e lo "trasporti" in una nuova posizione m nel numero? Oppure intendevi solo disattivarne uno (clear_bit()) e impostarne un'altro?

Ottimo ora provo :D
Cmq per lo scorrimento mi basta rimuoverne (non disattivare) uno e inserirne uno casuale alla fine.

[DanieleC88]

Ok, ma i bit meno significativi di quello che stai "rimuovendo" andrano spostati a sinistra tutti quanti... :D
Non è difficile da fare nemmeno quello, se ti serve una mano, dimmi pure. ;)

[Tommo]

Ok, ma i bit meno significativi di quello che stai "rimuovendo" andrano spostati a sinistra tutti quanti... :D
Non è difficile da fare nemmeno quello, se ti serve una mano, dimmi pure. ;)

Esatto è questo che mi manca :mc:

[variabilepippo]

In che modo sono memorizzati i bit (int, array, altro)?

[DanieleC88]

Esatto è questo che mi manca :mc:
Tu vuoi togliere, ad esempio, il decimo bit da un numero, e questo abbiamo già visto come si fa. Ora, come fai a prendere solo i bit da 0 a 8 (i 9 bit meno significativi del decimo)?
int mask = BIT(9) - 1;

menosignificativi = (numero & mask);
numero &= (~mask); /* pulisci i bit meno significativi del decimo */

menosignificativi <<= 1; /* shift a sinistra di una posizione */
numero |= menosignificativi | bitcambiato; /* il bit che vuoi impostare */


Effettivamente, se usi delle array invece di numeri interi, il discorso è simile, ma non puoi applicare gli operatori bitwise... ;)

[DanieleC88]

Ah, comunque, la macro che avevo messo prima, BIT_TEST(), può anche essere scritta così:
#define BIT_TEST(n, i) (((n) >> (i)) & 1)
che probabilmente è anche più efficiente.

[Tommo]

io memorizzo la sequenza di bit come unsigned char*, ma se necessario lo posso benissimo cambiare.

Sinceramente non ci sto capendo molto :D
Mi "studio" per bene gli esempi...

[DanieleC88]

Come unsigned char*? Quindi, un'array dinamica dove ogni cifra che usi è rappresentata da un byte? Allora i miei esempi non funzionano... :Prrr:

Gli esempi che io ti avevo fatto sfruttavano la rappresentazione dei numeri in binario naturale, quindi visti come un "numero"; se vuoi usare un'array come fai adesso, devi adattare un po' le cose che ti avevo scritto. ;)

[Tommo]

Come unsigned char*? Quindi, un'array dinamica dove ogni cifra che usi è rappresentata da un byte? Allora i miei esempi non funzionano... :Prrr:

Gli esempi che io ti avevo fatto sfruttavano la rappresentazione dei numeri in binario naturale, quindi visti come un "numero"; se vuoi usare un'array come fai adesso, devi adattare un po' le cose che ti avevo scritto. ;)

La mia idea era di usare proprio il binario naturale; solo che la sequenza è troppo lunga per stare in un solo numero; dovrebbero essere attorno ai 100 bits... ma dovrebbe comportarsi come un'unica sequenza, non come n chars.

[DanieleC88]

Quindi, hai un certo numero di celle di memoria contigue che contengono il numero codificato in binario naturale, per superare il massimo di 32 bit? Puoi usare una serie di unsigned int, così avrai 32 bit per ogni numero:
32 bit + 32 bit + 32 bit + 32 bit > 100 bit

Te ne basterebbero 4 per definire un numero "grosso" (ovviamente la quantità dipende dalla grandezza del tipo che usi: puoi saltare direttamente su un long se è più conveniente).

[marco.r]

Salve,
volevo accompagnare la tesina (si sono in ritardo bestia :D ) con una simpatica demo, dato che tutti portano powerpoint e io non mi sentivo da meno :D

Cmq apparte ciò, ho sviluppato un programmino bastanza semplice che simula l'evoluzione di "bestie", che vengono generate proceduralmente a partire da una stringa di bits, la quale viene modificata per delezione o modifica o crossover secondo lo standard degli algoritmi genetici.

Se le stringhe sono di dimensione variabile e devi poter togliere e aggiungere pezzi molto piu' semplice andare con un vector<bool>. A meno che la cosa non ti causi problemi di memoria probabilmente e' anche piu' veloce.

[Tommo]

Già... e in un array di quel tipo come potrei fare per invertire o rimuovere un bit arbitrario?
Ricapitolo gli esempi che non so se ci siamo intesi :D

-"mutazione"
01010101011011010101011001010010101001010100101010100101
|
v
01010101011011010101011011010010101001010100101010100101
bit evidenziato invertito

-"delezione"

010101010110110101010110X10100101010010101001010101001010
bit X rimosso, e aggiunto uno alla fine (0)

Cmq sperimentando ho notato che è meglio leggere a blocchi di float.
La sequenza sarebbe quindi un float[16], 512 bits.

Scusa l'accollo, ma mi potresti ricapitolare come fare le due operazioni? Mica ho capito :doh:

[marco.r]

-"delezione"

010101010110110101010110X10100101010010101001010101001010
bit X rimosso, e aggiunto uno alla fine (0)

Ah, quindi la dimensione e' fissa ? In tal caso bitset<> e' tuo amico...

[marco.r]

Già... e in un array di quel tipo come potrei fare per invertire o rimuovere un bit arbitrario?


Non e' molto difficile

-"mutazione"
01010101011011010101011001010010101001010100101010100101
|
v
01010101011011010101011011010010101001010100101010100101
bit evidenziato invertito


typedef vector<bool> Code;
void invert( Code& c, position p)
{
c[p] = !c[p];
}




-"delezione"

010101010110110101010110X10100101010010101001010101001010
bit X rimosso, e aggiunto uno alla fine (0)




void remove( Code& c, position p)
{
c.erase(p);
c.push_back( 0 );
}

[Tommo]

Ma un bool è grande un bit?
Credo di no, un vettore di bool non è equivalente ad un segmento di binario naturale... io avevo letto che un bool è cmq grande un byte.

Cmq si bitset è mio amico... pare faccia tutto quello che mi serve.
Ma da un bitset lungo 512, come faccio ad estrarre floats di 32 in 32?
Quello restituisce solo unsigned longs...

EDIT: Dunque, a quanto pare la cosa migliore è un array di bools, associati a 0 e 1. Mi rimane solo da capire come convertire questo binario "virtuale" in binario naturale, per estrarne dei floats...

Approccio che mi viene in mente: generare i floats in tempo reale, partendo da un float i cui bits sono tutti 0, e attivandoli uno ad uno con gli operatori bitwise, seguendo spezzoni del codice di bools.
Possibile?

[marco.r]

mi sfugge perche' tu voglia estrarre dei float :mbe:

[Tommo]

Scopo del programma :D
Questo "codice genetico" (non a caso ho parlato di mutazione e delezione) genera 16 variabili float che regolano la costituzione di un "bestio".
Quindi voglio implementare un classico algoritmo genetico.

EDIT: ecco, questo è codice per leggere un float dalla sequenza di bools:

//legge una cifra dalla sequenza
float read( unsigned int index )
{
float f = 0;

index *= 32;
for(unsigned int i = 0; i < 32; i++)
{
//la sequenza di bools sta in bases.
if( bases[index+i] )
f |= (1 << i);
else
f |= (0 << i);
}

return f;
}


Me lo confermate? :D

Mi manca quello per settare però... ma posso farne a meno, tanto i valori da settare sono random.

[Furla]

bases è un array di bool che ti puppa 1 byte per ogni bit, non so se conviene... dipende dalla dimensione massima di una stringa e da quante stringhe si possono avere contemporaneamente. l'operatore "|" funziona solo su tipi che rappresentano valori in notazione posizionale, quindi non sui float. non capisco proprio a cosa ti serva il float.

io trovo più semplice ragionare a oggetti, visto che usi il c++ potresti farti una classe tipo:

const int DIM = 16;
class bits
{
int b[DIM];
public:
bits(){for(int i=0;i<DIM;i++) b[i]=0;}
bool get(int i) {return b[i/32] & 1<<i%32;}
void set(bool a, int i) {
if (a) b[i/32] |= 1<<i%32;
else b[i/32] &= ~(1<<i%32);
}
void erase(int i) {
int n=i/32, d=i%32;
b[n] = b[n+1]<<31 | ~(1<<31) & b[n]>>1 & -1<<d | b[n] & ~(-1<<d);
while (++n<DIM-1) b[n]= b[n+1]<<31 | ~(1<<31) & b[n]>>1;
}
};


vector e altra robaccia dell'stl è veramente troppo pesante e inutile, ci vuole di più ad imparare ad usarli che a scrivere il codice da zero. ma se prevedi di fare spesso programmini del genere facci un pensierino...