Memorizzare più scelte in un solo numero intero: sfruttiamo il sistema binario !

Recentemente ho dovuto progettare un piccolo questionario che serve a configurare una serie di scelte in base a gusti e abitudini dell’intervistato. Per memorizzare le risposte date per ogni domanda, si potrebbe utilizzare un array di questo tipo:

int risposte[d] = n //numero della risposta data (da 1 a n)

In realtà in questo caso le risposte sarebbero esclusive: ne potrei memorizzare una sola per ogni domanda. Per catalogare più risposte avrò quindi bisogno di un array bidimensionale in cui salvare lo stato di ogni risposta:

boolean risposte[d][r] = vero/falso

Un array di variabili di tipo boolean fa proprio al caso nostro… o forse no ?

Sfruttiamo la potenza dei bit !

Dovendo memorizzare una serie di valori di tipo boolean, una soluzione più elegante potrebbe essere quella di sostituirli con un array di bit, o meglio sfruttare i singoli bit di una dword (32 bit) convertita in numero intero per conoscere lo stato delle risposte di ogni domanda:

int risposte[d] = n;

Sfruttando la rappresentazione binaria del numero intero n, possiamo abbinare le risposte ad un determinato bit, in questo modo:

risposta_1 = 0000 0000 0000 0001
risposta_2 = 0000 0000 0000 0010
risposta_3 = 0000 0000 0000 0100

risp.1+2+3 = 0000 0000 0000 0111

e combinarle mettendo a 1 il bit corrispondente. Il risultato sarà un numero intero che “nasconde” il risultato di ben 32 risposte (considerando un numero a 32 bit, o 16 bit per 16 risposte, come in tabella).

risposta_1 = 0000 0000 0000 0001 -> 1 decimale
risposta_2 = 0000 0000 0000 0010 -> 2
risposta_3 = 0000 0000 0000 0100 -> 4

risp.1+2+3 = 0000 0000 0000 0111 -> 1+2+4 = 7

Per memorizzare il valore di un singolo bit in un numero intero, useremo l’operatore a bit OR (|) per settarlo a 1:

risposte[d] = risposte[d] |= 1 << r;

e l’operatore AND (&) per resettarlo (scrivere zero):

risposte[d] = risposte[d] &= ~(1 << r);

dove r è il numero progressivo della risposta, da 0 a n, e quindi anche la posizione del bit nella dword. Nella variabile risposte[d] avremo dunque i risultati di tutte le risposte della relativa domanda d.

Infine, per leggere i valori delle risposte, useremo una semplice formula che sposta il bit interessato sulla destra della dword e lo confronta con un bit a 1 tramite l’operatore AND (&):

bit = (number >> r) & 1;

Vediamo queste formule tradotte in funzioni sfruttabili in un nostro programma, ad esempio in Javascript:

/*
* scrive un determinato bit in un numero intero
*
* bit_number:  posizione del bit, da 0 a n (15, 31 ...)
* bit_value: valore del bit: 0 / 1
* int_value: numero intero da modificare
*/
function setBit(bit_number, bit_value, int_value) {
 if (bit_value == 1)
   return int_value |= 1 << bit_number;
 else
  return int_value &= ~(1 << bit_number);
}


/*
* testa il valore di un determinato bit
*
* bit_number: posizione del bit, da 0 a n (15, 31 ...)
* int_value: numero intero da testare
*
* return true: bit a 1, false: bit a 0
*/
function isBitOn(bit_number, int_value) {
 return ((int_value >> bit_number) & 1) == 1;
}

A questo punto, per salvare lo stato delle risposte, basterà utilizzare la funzione setBit(...), e per leggerlo, la funzione isBitOn(...).

Più risposte valide per ogni scelta finale

Applicando questo metodo anche al criterio di scelta delle risposte finali del questionario, potremo creare un sistema che considera più risposte dell’utente come valide per selezionare un determinato risultato, assegnando ad ogni risposta utente un valore e calcolando infine i totali. Ad esempio, nel tentativo di indovinare il tipo di auto che serve a chi fa il questionario, potrei chiedere quanti chilometri vengono percorsi ogni anno, considerando valide tutte le risposte in caso di motore a GPL, mentre solo i bassi chilometraggi per il motore a benzina e gli alti per il gasolio. Con le domande successive poi andrò a definire meglio le scelte, chiedendo ad esempio se si ha un tipo di guida scattante e veloce (benzina), o tranquilla (GPL), oppure se si fa tanta autostrada (gasolio e GPL) o solo città (benzina e GPL). Insomma più risposte per uno o più prodotti, il tutto memorizzabile in pochi numeri interi.

Un prodotto la cui selezione dipende da più risposte verrà rappresentato dal loro relativo valore binario: su 4 risposte, se la scelta del prodotto dovesse dipendere dalla prima, dalla seconda o dalla quarta, basterà assegnargli il valore binario 1011, ovvero 4+2+1 = 7. In fase di ricerca delle corrispondenze ci basterà confrontare il risultato con il valore di scelta del prodotto utilizzando l’AND bit a bit (&):

risultato = risposte & scelta_prodotto;

Nella variabile risultato avrò il risultato del confronto bit a bit prodotto dall’operatore AND, che restituisce 1 solo quando i bit a confronto sono entrambi a 1:

risposte         = 0000 0000 0000 1010
                      bitwise AND
scelta_prodotto  = 0000 0000 0000 1011
                      risultato:
risultato        = 0000 0000 0000 1010

Contando i bit a 1 della variabile risultato otterrò il punteggio prodotto dal confronto, e quindi l’incidenza della scelta, che potrà infine essere confrontata con altre scelte per elencarle in ordine di pertinenza o selezionare quella col punteggio più alto. Se come risultato ottengo zero, significa quindi che nessuna risposta si adatta al prodotto in esame.

/*
* conta i bit a 1 del numero passato, per una data dimensione in bit
*
* int_value: numero intero da esaminare in formato binario
* size: numero di bit da confrontare
*/
function bit1Count(int_value, size) {
  var count = 0;
  for (var i=0; i<size; i++) {
    if (isBitOn(i, int_value))
      count++;
  }
  return count;
}

punteggio = bit1Count(risultato, numero_risposte);

Un piccolo esempio in javascript e html

Creiamo una semplice paginetta in html che permette di selezionare più risposte e ne visualizza i risultati su richiesta, sfruttando le funzioni viste poco fa.

Per vedere l’esempio clicca qui
Per scaricare il codice dell’esempio clicca qui

Avremo bisogno di 2 file: index.html e main.js. In quest’ultimo inseriremo le nostre funzioni di raccolta dati e conversione, e la funzione che visualizzerà gli id delle risposte selezionate e il risultato del questionario.

L’esempio è molto semplice e ho evitato apposta di creare un questionario dinamico, ma ovviamente è possibile farlo impostando un array bidimensionale con testi delle domande e delle risposte, o utilizzando Json o xml per parametrizzare i dati, per poi creare in tempo reale la relativa tabella con i check-box. Così facendo potremmo facilmente visualizzare i testi delle risposte selezionate anziché i relativi id.

Mancano anche diversi controlli, soprattutto sull’incidenza delle risposte per la selezione del risultato finale, ma l’essenza dell’esempio è mirata alla collezione e al confronto dei valori binari, cosa che viene svolta egregiamente dalle funzioni che vedremo.

Il codice di Index.html

Creiamo il file index.html e apriamolo col nostro editor preferito. Il codice è semplicissimo e serve a visualizzare il testo delle 2 domande e i check-box relativi alle risposte, oltre ad includere il file main.js.

Un ottimo editor per tutti i tipi di file è EmEditor.

<html>
<body>
 
 <div id="survey">
 <br>Che trasmissioni ti piacciono ?
 <br><input type="checkbox" id="chk-1-1" onClick="setAnswer(this, 1,1)">Film
 <br><input type="checkbox" id="chk-1-2" onClick="setAnswer(this, 1,2)">Documentari
 <br><input type="checkbox" id="chk-1-3" onClick="setAnswer(this, 1,3)">Sport
 <br><input type="checkbox" id="chk-1-4" onClick="setAnswer(this, 1,4)">Cartoni animati
 <br><input type="checkbox" id="chk-1-5" onClick="setAnswer(this, 1,5)">Telefilm
 <br>
 <br>Quali argomenti segui ?
 <br><input type="checkbox" id="chk-2-1" onClick="setAnswer(this, 2,1)">Fantascienza
 <br><input type="checkbox" id="chk-2-2" onClick="setAnswer(this, 2,2)">Scienza
 <br><input type="checkbox" id="chk-2-3" onClick="setAnswer(this, 2,3)">Cronaca
 <br><input type="checkbox" id="chk-2-4" onClick="setAnswer(this, 2,4)">Fantasy
 <br><input type="checkbox" id="chk-2-5" onClick="setAnswer(this, 2,5)">Storia
 </div>
 <br>
 <br>
 <input type="button" value="visualizza risposte" onClick="printResults();">
</body>

<script src="main.js"></script> 
</html>

Ogni check-box chiama la funzione setAnswer(checkbox, domanda, risposta) che verificherà lo stato dello stesso check-box (il parametro this) e imposterà il bit della risposta di conseguenza. Per identificare domanda e risposta vengono passati i relativi id.

Infine aggiungiamo un pulsante (button) che dovrà chiamare la funzione dedicata alla visualizzazione dei risultati: printResults();

Il codice di main.js

Le scelte finali, rappresentate da alcune parole che alla fine comporranno una frase, vengono selezionate dalla app in base alle risposte, e sono memorizzate in 2 array bidimensionali: scelte[][] e scelteTxt[][], in modo da gestire un risultato per ogni domanda. Dunque abbiamo l’array scelte[domanda][parola] che contiene i valori interi che rappresentano i bit relativi alle risposte plausibili per la scelta in esame, pronti da confrontare con la word composta dai bit delle risposte in esame. Anche in questo caso potremmo usare un file Json esterno per parametrizzare i risultati e rendere la nostra app dinamica e facilmente configurabile.

Dunque gli elementi che ci servono sono:

  • funzione setAnswer(checkbox, domanda, risposta) per memorizzare lo stato dei checkbox
  • funzione printResults(), per calcolare i risultati e visualizzare a video
  • funzioni di calcolo e confronto isBitOn()setBit() e bit1Count()
  • risposte[d]: l’array contenente le risposte per tutte le domande
  • scelteTxt[d][s]: i testi che rappresentano le scelte da visualizzare come risultato del questionario: un set di n testi per ogni domanda
  • scelte[d][s]: per ogni domanda, ogni scelta è rappresentata dai bit delle risposte plausibili
'use strict';

// è possibile creare dinamicamente le risposte in html e dimensionare di conseguenza l'array
// per il nostro esempio useremo una struttura statica
var risposte = [0,0];

// preparo un array di scelte finali che dipendono dalle risposte.
// i numeri sono la rappresentazione decimale dei bit delle risposte.
// Ad esempio: 3 = 0011 = 1+2 = risposte 1 e 2
// 24 = 1100 = 8+16 = risposte 3 e 4
var scelte = [ [3,4,24],
               [20,9,6]
             ];
// creo anche un array con i testi delle scelte finali
var scelteTxt = [ ['impegnata', 'sportiva', 'leggera'],
                  ['realistico', 'fantasioso', 'curioso']
                ];



// tramite lo stato del checkBox posso sapere se settare a 1 o resettare il bit corrispondente alla risposta data
function setAnswer(theCheckBox, question, answer) {
   risposte[question-1] = setBit(answer-1, theCheckBox.checked?1:0, risposte[question-1])
}


// visualizzo gli ID delle risposte date e le relative scelte
function printResults() {
 
 // colleziono gli ID delle risposte, per visualizzarli a titolo informativo
 var html = 'risposte selezionate: ';
 for (var d=0; d<risposte.length; d++) {
   for (var r=0; r<5; r++)
     if (isBitOn(r, risposte[d]))
       html = html + ' ' + (d+1) + '/' + (r+1) + ' ';
 }
 
 
 // creo la frase finale contenente le 2 parole scelte in base alle risposte date
 var risultati = [0,0];
 var idx = 0;
 for (var i=0; i<scelte.length; i++) {
   for (var a=0; a<scelte[i].length; a++) {
     var res = risposte[i] & scelte[i][a];
     var punteggio = bit1Count(res, 5);
     // seleziono la scelta con maggiore incidenza
     if (risultati[i] < punteggio) {
       risultati[i] = punteggio;
       idx = a;
     }
   }
   if (i==0)
     html = html + '\nTi piace la TV *' + scelteTxt[i][idx] + '*';
   else
     html = html + ' e sei un tipo *' + scelteTxt[i][idx] + '*';
  }
  alert(html);
}


/*
* testa il valore di un determinato bit
*
* bit_number: posizione del bit, da 0 a n (15, 31 ...)
* int_value: numero intero da testare
*
* return true: bit a 1, false: bit a 0
*/
function isBitOn(bit_number, int_value) {
 return ((int_value >> bit_number) & 1) == 1;
}


/*
* scrive un determinato bit in un numero intero
*
* bit_number: posizione del bit, da 0 a n (15, 31 ...)
* bit_value: valore del bit: 0 / 1
* int_value: numero intero da modificare
*/
function setBit(bit_number, bit_value, int_value) {
 if (bit_value == 1)
   return int_value |= 1 << bit_number;
 else
   return int_value &= ~(1 << bit_number);
}



/*
* conta i bit a 1 del numero passato, per una data dimensione in bit
*
* int_value: numero intero da esaminare in formato binario
* size: numero di bit da confrontare
*/
function bit1Count(int_value, size) {
 var count = 0;
 for (var i=0; i<size; i++) {
   if (isBitOn(i, int_value))
     count++;
 }
 return count;
}


Come si può vedere dal codice, printResults() mette insieme le nostre teorie andando a recuperare le risposte memorizzate nei due valori interi contenuti nell’array risposte[] e visualizzando i singoli risultati tramite la funzione isBitOn(id_risposta, valore_risposte).

Il ciclo successivo confronta ogni risposta ( risposte[] ) con i valori relativi alle scelte possibili ( scelte[][] ), Per ciascuna domanda, esegue l’AND a bit ( & ) tra tale valore e il valore delle risposte, e utilizza la funzione bit1Count(valore, numero_bits) per contare il numero di corrispondenze cercando nei 2 valori i bit a 1 nella stessa posizione.

Certo la selezione dei risultati lascia ancora un po’ a desiderare, la i nostri confronti funzionano alla perfezione, e alla fine siamo riusciti a gestire diverse informazioni utilizzando un set minimo di variabili intere, risparmiando in array, loop e memoria.

Numeri decimali e numeri binari

Ragionando per numeri interi, sui valori che abbiamo trattato finora, in pratica le risposte vengono abbinate a questa sequenza di numeri:

1,2,4,8,16,32,64,128 ... 16384, 32768 (16 bit)

e quando ne viene selezionata più di una, il numero risultante è la somma dei sopracitati interi. Ad esempio, se scelgo la risposta 1 e 2:

1+2 = 3

Dunque, ponendo un risultato pari a 6, potremo determinare quali risposte sono state date:

1+2+3 = 6

In pratica, partendo da 1, ogni numero successivo viene calcolato moltiplicando per 2 il numero precedente. Considerando p = posizione da 1 a 16 nel numero binario a 16 bit (o 32 per 32 bit), il numero decimale corrispondente si calcola così:

dec = 1 x 2p

Difatti, per trasformare un numero binario in decimale, ad esempio 11001 (25), dovremo fare la somma dei valori dei singoli bit:

1x24 + 1x23 + 0x22 + 0x21 + 1x20 = 25

che equivale a fare:

1x16 + 1x8 + 0x4 + 0x2 + 1x1 = 25

Allo stesso modo, per convertire da decimale a binario, dovremo continuare a dividere per 2 il nostro numero, annotando il resto (0 o 1), finché non ci troveremo ad ottenere zero come risultato:

25/2 = 12 -> avanzo 1
12/2 =  6 -> avanzo 0
 6/2 =  3 -> avanzo 0
 3/2 =  1 -> avanzo 1
 1/2 =  0 -> avanzo 1

25(10) = 11001(2)

Una volta impostati i nostri numeri binari, potremo manipolarli a piacere tramite gli operatori a bit AND, OR, XOR e NOT, e le operazioni di bit shifting << e >>.

Gli operatori a bit

Prova gli operatori a bit con il calcolatore
Per scaricare il codice del calcolatore clicca qui

Abbiamo già utilizzato questi operatori per il confronto delle risposte nella funzione isBitOn(…)  e setBit(…), ora vediamo in dettaglio come funzionano.

Left shift ( << )

usando questo operatore possiamo far slittare tutti i bit a sinistra di un determinato numero di posizioni n, ottenendo un intero che è il numero base moltiplicato per 2n, senza però andare ad impegnare la cpu con calcoli esponenziali: lo shift di bit è un’operazione eseguita direttamente sulla posizione dei bit nell’area di memoria in cui si trova il byte / word / dword in questione.

25 << 1 = 50
prima:  25(10) = 0000 0000 0001 1001
dopo:   50(10) = 0000 0000 0011 0010
25 << 1 = 25*21 = 50

25 << 2 = 100
prima:  25(10) = 0000 0000 0001 1001
dopo:  100(10) = 0000 0000 0110 0100
25 << 2 = 25*22 = 100
25 << 3 = 25*23 = 200
25 << 4 = 25*24 = 400

Right shift ( >> )

Esegue l’operazione opposta, spostando i bit verso destra. Il bit zero (a destra) sparirà, il bit 1 diventerà bit zero, il 2 diventerà l’1 e così via. Il calcolo decimale corrispondente è la divisione per 2 ed esponenti di 2, dove l’esponente x è pari al numero di bit shiftati (perdendo le eventuali cifre dopo la virgola). I bit mancanti a sinistra verranno riempiti con degli zeri, preservando comunque il segno (+/-) del numero originario.

25 >> 1 = 12
prima:  25(10) = 0000 0000 0001 1001
dopo:   12(10) = 0000 0000 0000 1100
25 << 1 = 25/21 = 12

25 << 2 = 100
prima:  25(10) = 0000 0000 0001 1001
dopo:    6(10) = 0000 0000 0000 0110
25 << 2 = 25/22 =  6
25 << 3 = 25*23 =  3
25 << 4 = 25*24 =  1

Right shift logico ( >>> )

Come il right shift aritmetico, questo operatore fa slittare a destra i bit di un dato numero di posizioni, ma tenderà a riempire gli spazi a sinistra con il valore del bit più significativo (dedicato al segno +/-). Ciò significa che sin caso di numeri negativi otterremo risultati molto differenti. Facciamo qualche test sui numeri negativi con il calcolatore per vedere le differenze.

Operatore NOT ( ~ )

Questo operatore confronta un bit e restituisce il suo opposto. Zero diventa 1 e 1 diventa zero.

~0 = 1
~1 = 0

Operatore a bit AND ( & )

Questo operatore confronta due valori binari bit per bit, restituendo un 1 quando tutti e 2 i bit a confronto sono a 1, altrimenti ritorna zero.

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
    0000 0000 0001 1001 (25(10))
AND 0000 0000 0000 1100 (12(10))
  = 0000 0000 0000 1000 (8(10))
    0000 0001 0111 0011 (371(10))
AND 0000 0000 1111 1111 (255(10))
  = 0000 0000 0111 0011 (115(10))

Operatore a bit OR ( | )

L’operatore OR logico confronta 2 bit e restituisce zero solo se tutti e 2 i bit sono a zero. In pratica se c’è un 1, il risultato sarà sempre 1.

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
    0000 0000 0001 1001 (25(10))
OR  0000 0000 0000 1100 (12(10))
  = 0000 0000 0001 1101 (29(10))
    0000 0001 0111 0011 (371(10))
OR  0000 0000 1111 1111 (255(10))
  = 0000 0001 1111 1111 (511(10))

Operatore a bit XOR ( ^ )

L’operatore XOR confronta 2 bit e restituisce zero solo se i 2 bit sono uguali. Quindi il risultato sarà 1 quando solo uno dei 2 bit è a 1.

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
    0000 0000 0001 1001 (25(10))
OR  0000 0000 0000 1100 (12(10))
  = 0000 0000 0001 0101 (21(10))
    0000 0001 0111 0011 (371(10))
OR  0000 0000 1111 1111 (255(10))
  = 0000 0001 1000 1100 (396(10))

 

 

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *