¿Existe un límite práctico para el tamaño de las máscaras de bits?

Question

Hay una forma común de almacenar varios valores en una variable, utilizando una máscara de bits. Por ejemplo, si un usuario tiene privilegios de lectura, escritura y ejecución en un elemento, que se puede convertir en un solo número diciendo read = 4 (2 ^ 2), write = 2 (2 ^ 1), execute = 1 (2 ^ 0) y luego agréguelos para obtener 7.

Utilizo esta técnica en varias aplicaciones web, donde generalmente almacenaba la variable en un campo y le daba un tipo de MEDIUMINT o lo que sea, dependiendo del número de valores diferentes.

Lo que me interesa es si existe o no un límite práctico para la cantidad de valores que puede almacenar de esta manera. Por ejemplo, si el número era superior a 64, ya no se podían usar enteros (64 bits). Si este fuera el caso, ¿qué usarías? ¿Cómo afectaría a la lógica de su programa (es decir, podría seguir utilizando comparaciones a nivel de bits)?

Sé que una vez que comience a obtener conjuntos de valores realmente grandes, un método diferente sería la solución óptima, pero estoy interesado en los límites de este método.

Answer 1

Fuera de la parte superior de mi cabeza, escribiría una función set_bit y get_bit que podría tomar una matriz de bytes y un bit de desplazamiento en la matriz, y usar algunos cambios de bits para establecer / obtener el bit apropiado en la matriz. Algo como esto (en C, pero espero que tengas la 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

He usado máscaras de bits en el código del sistema de archivos donde la máscara de bits es muchas veces más grande que una palabra de máquina. Piénsalo como una "matriz de booleanos";

(agrupar máscaras en memoria flash si quieres saberlo)

muchos compiladores saben cómo hacer esto por usted . Adda bit de código OO para tener tipos que operen de manera sensible y luego su código comienza a parecer que es un intento, no un poco de bit banging.

Mis 2 centavos.

Answer 3

Con un entero de 64 bits, puede almacenar valores de hasta 2 ^ 64-1, 64 es solo 2 ^ 6. Así que sí, hay un límite, pero si necesita más de 64 banderas, me gustaría saber qué hacían todos :)

¿En cuántos estados tienes que pensar potencialmente? Si tiene 64 estados potenciales, la cantidad de combinaciones en las que pueden existir es el tamaño completo de un entero de 64 bits.

Si necesita preocuparse por 128 banderas, entonces un par de vectores de bits será suficiente (2 ^ 64 * 2).

Adición : en Perlas de programación, hay una discusión extensa sobre el uso de una matriz de bits de longitud 10 ^ 7, implementada en números enteros (para mantener los 800 números usados): es muy rápida y muy apropiada para la tarea descrita en ese capítulo.

Answer 4

Algunos lenguajes (creo que Perl no lo hace, no estoy seguro) permiten la aritmética bit a bit en cadenas. Dándole un rango efectivo mucho mayor. ((strlen * caracteres de 8 bits) combinaciones)

Sin embargo, no usaría un solo valor para la superposición de más de un / tipo / de datos. El triplete básico r / w / x de las entradas de 3 bits probablemente sería el "práctico" superior. Límite, no por razones de eficiencia espacial, sino por razones prácticas de desarrollo.

(Php usa este sistema para controlar sus mensajes de error, y ya descubrí que es un poco exagerado cuando tienes que definir valores donde las constantes de php no son residentes y tienes que generar el número entero a mano y, para ser sincero, si chmod no fuera compatible con la sintaxis de estilo 'ugo + rwx', nunca querría usarla porque nunca puedo recordar los números mágicos)

En el instante en que tiene que abrir una tabla de constantes para depurar el código, sabe que ha ido demasiado lejos.

Answer 5

Hilo antiguo, pero vale la pena mencionar que hay casos que requieren máscaras de bits hinchadas, por ejemplo, huellas digitales moleculares, que a menudo se generan como matrices de 1024 bits que hemos empaquetado en 32 campos bigint (SQL Server no admite UInt32). Las operaciones poco inteligentes funcionan bien, hasta que su mesa comienza a crecer y se da cuenta de la lentitud de las llamadas a funciones separadas. El tipo de datos binarios funcionaría si no fuera por la prohibición de T-SQL en operadores bitwise que tienen dos operandos binarios.

Answer 6

Por ejemplo .NET usa una matriz de enteros como almacenamiento interno para su clase BitArray. Prácticamente no hay otra forma de evitarlo.

Dicho esto, en SQL necesitará más de una columna (o usar BLOBS) para almacenar todos los estados.

Answer 7

Ha marcado esta pregunta SQL, por lo que creo que debe consultar la documentación de su base de datos para encontrar el tamaño de un entero. Luego reste un bit para el signo, solo para estar seguro.

Editar: Tu comentario dice que estás usando MySQL. La documentación de MySQL 5.0 Numeric Tipos establece que El tamaño máximo de un NUMERIC es de 64 o 65 dígitos. Eso es 212 bits para 64 dígitos.

Recuerde que su idioma de elección debe ser capaz de trabajar con esos dígitos, por lo que puede estar limitado a un entero de 64 bits de todos modos.