Existe-t-il une limite pratique à la taille des masques de bits?

Question

Il existe un moyen courant de stocker plusieurs valeurs dans une variable, en utilisant un masque de bits. Par exemple, si un utilisateur a des privilèges de lecture, d'écriture et d'exécution sur un élément, celui-ci peut être converti en un seul numéro en indiquant read = 4 (2 ^ 2), write = 2 (2 ^ 1), execute = 1 (2 ^ 0) puis additionnez-les pour obtenir 7.

J'utilise cette technique dans plusieurs applications Web, où je stockais généralement la variable dans un champ et lui donnais le type MEDIUMINT ou autre, selon le nombre de valeurs différentes.

Ce qui m'intéresse, c'est de savoir s'il existe ou non une limite pratique au nombre de valeurs que vous pouvez stocker de cette façon? Par exemple, si le nombre était supérieur à 64, vous ne pourriez plus utiliser d’entiers (64 bits). Si c'était le cas, qu'utiliseriez-vous? Comment cela affecterait-il la logique de votre programme (par exemple: pourriez-vous toujours utiliser des comparaisons au niveau des bits)?

Je sais qu'une fois que vous commencez à obtenir de très grands ensembles de valeurs, une méthode différente serait la solution optimale, mais les limites de la cette méthode m'intéressent.

Answer 1

De mémoire, j'écrirais une fonction set_bit et get_bit pouvant prendre un tableau d'octets et un décalage binaire dans le tableau, et utiliser un peu de bidouillage pour définir / obtenir le bit approprié dans le tableau. Quelque chose comme ça (en C, mais j'espère que vous avez l'idée):

// 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

J'ai utilisé des masques de bits dans le code du système de fichiers où le masque de bits est plusieurs fois plus gros qu'un mot machine. Pensez-y comme un "tableau de booléens";

(masques de journalisation en mémoire flash si vous voulez savoir)

beaucoup de compilateurs savent comment faire cela pour vous . Ajoutez un peu de code OO pour avoir des types qui fonctionnent de manière sensible, puis votre code commencera à ressembler à son intention, pas à un jeu d'enfant.

Mes 2 cents.

Answer 3

Avec un entier de 64 bits, vous pouvez stocker des valeurs allant jusqu'à 2 ^ 64-1, 64 seulement 2 ^ 6. Donc oui, il y a une limite, mais si vous avez besoin de plus de 64 drapeaux, je serais très intéressé de savoir ce qu'ils faisaient tous:)

À combien d’états avez-vous potentiellement besoin de réfléchir? Si vous avez 64 états potentiels, le nombre de combinaisons dans lesquelles ils peuvent exister est la taille complète d'un entier 64 bits.

Si vous avez besoin de vous préoccuper de 128 indicateurs, une paire de vecteurs bits suffira (2 ^ 64 * 2).

Ajout : dans Programming Pearls, il est beaucoup question d'utiliser un tableau de bits de longueur 10 ^ 7, implémenté dans des entiers (pour conserver les 800 numéros utilisés) - c'est très rapide et très approprié pour la tâche décrite dans ce chapitre.

Answer 4

Certaines langues (je pense que perl le fait, je ne le sais pas) autorisent l’arithmétique au niveau des bits sur les chaînes. En vous donnant une gamme efficace beaucoup plus grande. ((strlen * caractères 8 bits) combinaisons)

Cependant, je ne voudrais pas utiliser une seule valeur pour la superposition de plus d'un / type / de données. Le triplet r / w / x de base des inits de 3 bits serait probablement le "plus pratique" supérieur limite, pas pour des raisons d'efficacité de l'espace, mais pour des raisons de développement pratiques.

(Php utilise ce système pour contrôler ses messages d'erreur, et j'ai déjà trouvé que c'était un peu exagéré quand vous devez définir des valeurs où les constantes de php ne sont pas résidentes et que vous devez générer l'entier à la main , et pour être honnête, si chmod ne supportait pas la syntaxe de style 'ugo + rwx', je ne voudrais jamais l'utiliser car je ne me souviendrai jamais des nombres magiques)

Dès l'instant où vous devez ouvrir un tableau de constantes pour déboguer du code, vous savez que vous êtes allé trop loin.

Answer 5

Ancien fil de discussion, mais il convient de mentionner qu'il existe des cas nécessitant des masques de bits gonflés, par exemple des empreintes moléculaires, qui sont souvent générés sous forme de tableaux de 1024 bits que nous avons regroupés dans 32 champs bigint (SQL Server ne prenant pas en charge UInt32). Les opérations par bits fonctionnent correctement - jusqu'à ce que votre table commence à se développer et que vous réalisiez la lenteur des appels de fonction séparés. Le type de données binaires fonctionnerait, ne serait-ce que si T-SQL avait interdit les opérateurs au niveau des bits ayant deux opérandes binaires.

Answer 6

Par exemple, .NET utilise un tableau d’entiers en tant que stockage interne pour leur classe BitArray. Pratiquement, il n'y a pas d'autre moyen.

Cela étant dit, en SQL, vous aurez besoin de plus d'une colonne (ou vous utiliserez les BLOBS) pour stocker tous les états.

Answer 7

Vous avez balisé cette question en SQL. Je pense donc que vous devez consulter la documentation de votre base de données pour trouver la taille d'un entier. Puis soustrayez un bit pour le signe, juste pour être sûr.

Modifier: votre commentaire indique que vous utilisez MySQL. La documentation relative aux types numériques MySQL 5.0 indique que le type la taille maximale d'un NUMERIC est de 64 ou 65 chiffres. C'est 212 bits pour 64 chiffres.

N'oubliez pas que la langue de votre choix doit pouvoir utiliser ces chiffres, de sorte que vous pouvez quand même être limité à un entier 64 bits.