Esiste un limite pratico alla dimensione delle maschere di bit?

Question

Esiste un modo comune per memorizzare più valori in una variabile, usando una maschera di bit. Ad esempio, se un utente ha letto, scrive ed esegue i privilegi su un elemento, che può essere convertito in un singolo numero dicendo read = 4 (2 ^ 2), write = 2 (2 ^ 1), execute = 1 (2 ^ 0) e poi aggiungili insieme per ottenere 7.

Uso questa tecnica in diverse applicazioni Web, in cui di solito memorizzerei la variabile in un campo e le darei un tipo di MEDIUMINT o altro, a seconda del numero di valori diversi.

Quello che mi interessa, è se esiste o meno un limite pratico al numero di valori che è possibile memorizzare in questo modo? Ad esempio, se il numero era superiore a 64, non è più possibile utilizzare numeri interi (64 bit). Se così fosse, cosa useresti? In che modo influirebbe sulla logica del programma (ovvero: potresti ancora utilizzare confronti bit per bit)?

So che una volta che inizi a ottenere insiemi di valori davvero grandi, un metodo diverso sarebbe la soluzione ottimale, ma sono interessato ai limiti di questo .

Answer 1

In cima alla mia testa, scriverei una funzione set_bit e get_bit che potrebbe prendere una matrice di byte e un po 'di offset nella matrice, e usare alcuni bit-twiddling per impostare / ottenere il bit appropriato nell'array. Qualcosa del genere (in C, ma spero che tu abbia l'idea):

// sets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// result is 0 on success, non-zero on failure (offset out-of-bounds)
int set_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //set the right bit
  bytes[offset >> 3] |= (1 << (offset & 0x7));

  return 0; //success 
}

//gets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// returns (-1) on error, 0 if bit is "off", positive number if "on"
int get_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //get the right bit
  return (bytes[offset >> 3] & (1 << (offset & 0x7));
}

Answer 2

Ho usato le maschere di bit nel codice del filesystem in cui la maschera di bit è molte volte più grande di una parola macchina. pensalo come un "array di booleani";

(se vuoi sapere le maschere di journaling nella memoria flash)

molti compilatori sanno come farlo per te . Aggiungete un po 'di codice OO per avere tipi che funzionino correttamente e quindi il vostro codice inizia a sembrare come se fosse intento, non un po' di bit-bang.

I miei 2 centesimi.

Answer 3

Con un numero intero a 64 bit, è possibile memorizzare valori fino a 2 ^ 64-1, 64 è solo 2 ^ 6. Quindi sì, c'è un limite, ma se hai bisogno di più di 64 bandiere di valore, sarei molto interessato a sapere cosa stavano facendo tutti :)

Di quanti stati quindi devi potenzialmente pensare? Se hai 64 stati potenziali, il numero di combinazioni in cui possono esistere è la dimensione completa di un numero intero a 64 bit.

Se devi preoccuparti di 128 flag, allora sarebbe sufficiente un paio di bit bit (2 ^ 64 * 2).

Aggiunta : in Programming Pearls, c'è una discussione estesa sull'uso di un array di bit di lunghezza 10 ^ 7, implementato in numeri interi (per contenere 800 numeri usati) - è molto veloce e molto appropriato per l'attività descritta in quel capitolo.

Answer 4

Alcune lingue (credo che Perl non lo sappia) permettono l'aritmetica bit a bit sulle stringhe. Dandoti un raggio d'azione molto maggiore. ((strlen * 8bit chars) combinazioni)

Tuttavia, non userei un singolo valore per la sovrapposizione di più di un / tipo / di dati. La tripletta r / w / x di base di ints a 3 bit sarebbe probabilmente la "pratica" superiore limite, non per motivi di efficienza dello spazio, ma per motivi di sviluppo pratico.

(Php usa questo sistema per controllare i suoi messaggi di errore, e ho già scoperto che è un po 'esagerato quando devi definire valori in cui le costanti di php non sono residenti e devi generare l'intero a mano e, a dire il vero, se chmod non supportasse la sintassi di stile 'ugo + rwx' non avrei mai voluto usarlo perché non ricordo mai i numeri magici)

Nell'istante in cui devi aprire una tabella delle costanti per eseguire il debug del codice, sai che sei andato troppo lontano.

Answer 5

Vecchio thread, ma vale la pena ricordare che ci sono casi che richiedono maschere bit gonfiate, ad esempio impronte digitali molecolari, che sono spesso generate come array a 1024 bit che abbiamo impacchettato in 32 campi bigint (SQL Server non supporta UInt32). Le operazioni a bit saggio funzionano bene - fino a quando la tabella non inizia a crescere e ti rendi conto della lentezza delle chiamate di funzioni separate. Il tipo di dati binari funzionerebbe, se non fosse per il divieto di T-SQL di operatori bit a bit con due operandi binari.

Answer 6

Ad esempio .NET utilizza un array di numeri interi come memoria interna per la loro classe BitArray. Praticamente non c'è altro modo.

Detto questo, in SQL avrai bisogno di più di una colonna (o di usare BLOBS) per memorizzare tutti gli stati.

Answer 7

Hai taggato questa domanda SQL, quindi penso che devi consultare la documentazione del tuo database per trovare la dimensione di un numero intero. Quindi sottrai un bit per il segno, solo per sicurezza.

Modifica: il tuo commento dice che stai usando MySQL. La documentazione per MySQL 5.0 Tipi numerici afferma che il la dimensione massima di un NUMERICO è di 64 o 65 cifre. Sono 212 bit per 64 cifre.

Ricorda che la tua lingua preferita deve essere in grado di lavorare con quelle cifre, quindi potresti comunque essere limitato a un numero intero a 64 bit.