iOS/Objective-C: Tengo una gran matriz de valores booleanos.¿Cómo implemento una matriz de bits en C/Objetivo C
Esta es una forma ineficiente de almacenar estos valores: se utilizan al menos ocho bits para cada elemento cuando solo se necesita uno.
¿Cómo puedo optimizar?
ver CFMutableBitVector/CFBitVector para una opción CFType
http://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBitVectorRef/Reference/reference.html – JeremyP
Pero esas clases almacenan objetos CFBit, que son typedeffed a 32 bit ints. Entonces esta solución desperdicia tanta memoria. –
@whitman los valores se pasan como CFBit; eso no quiere decir que estén * almacenados * como tales. Acabo de ver la implementación de CFBitVector (r.550.13). el consumo de memoria es de un bit, mientras que los tamaños de las asignaciones se redondean a un número divisible por 64. una implementación muy conservadora en general. – justin
Utiliza las operaciones lógicas bit a bit y el cambio de bit. (Una búsqueda en Google de estos términos podría darle algunos ejemplos.)
Básicamente se declara un tipo entero (incluyendo int, char, etc.), entonces los valores enteros "SHIFT" para el bit deseado, y después lo hace un OR o un AND con el número entero.
Algunos ejemplos ilustrativos rápidos (en C++):
inline bool bit_is_on(int bit_array, int bit_number)
{
return ((bit_array) & (1 << bit_number)) ? true : false;
}
inline void set_bit(int &bit_array, int bit_number)
{
bit_array |= (1 << bit_number);
}
inline void clear_bit(int &bit_array, int bit_number)
{
bit_array &= ~(1 << bit_number);
}
en cuenta que este ofrece "conjuntos de bits" de tamaño constante (sizeof(int) * 8 bits). Quizás esté bien para ti, o tal vez quieras construir algo además de esto. (O reutilice cualquier biblioteca que proporcione)
Esto utilizará menos memoria que las matrices bool ... SIN EMBARGO ... El código que el compilador genera para acceder a estos bits será más grande y más lento. Por lo tanto, a menos que tenga una gran cantidad de objetos que necesiten contener estas matrices de bits, podría tener un impacto neto negativo en el uso de la velocidad y la memoria.
La pregunta no tiene la etiqueta C++. Tal vez debería convertir su código a C. – JeremyP
@JeremyP - De todos modos, fue un ejemplo ilustrativo. Decidí usar referencias en lugar de punteros porque pensé que distraería menos de la pregunta que se hacía. Creo que el punto se entendió bien, y la respuesta no estaba destinada a copiarse en la solución de alguien de todos modos. – asveikau
la pregunta es sobre C. El interrogador puede que ni siquiera sepa qué es una referencia. Si ese es el caso, no has distraído menos, has distraído más. – JeremyP
Prueba esto:
#define BITOP(a,b,op) \
((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))
Entonces para cualquier matriz de elementos de enteros sin signo de no más grandes que size_t, la BITOP macro puede acceder a la matriz como una matriz de bits . Por ejemplo:
unsigned char array[16] = {0};
BITOP(array, 40, |=); /* sets bit 40 */
BITOP(array, 41, ^=); /* toggles bit 41 */
if (BITOP(array, 42, &)) return 0; /* tests bit 42 */
BITOP(array, 43, &=~); /* clears bit 43 */
etc.
Y reemplace los 8 con 'CHAR_BIT' si le importa la portabilidad completa de cualquier entorno C. –
En realidad, 8 funciona bien en cualquier lugar si no te molesta perder bits en plataformas donde 'CHAR_BIT> 8', y dará un mejor rendimiento que introducir cosas como división por 9 o 10 ... –
Para admitir la operación clara y = ~ que son dos operadores, & = y ~, debe envolver la segunda mitad de la macro en otro conjunto de parens. De lo contrario, escribes algo que no quieres decir. '#define BITOP (a, b, op) ((a) [(size_t) (b)/(8 * sizeof * (a))] op ((size_t) 1 << ((size_t) (b)% (8 * sizeof * (a))))) ' –
me encontré con esta pregunta ya que estoy escribiendo un marco matriz de bits que es la intención de gestionar grandes cantidades de 'bits' similar a Java BitSet. Estaba buscando para ver si el nombre que decidí estaba en conflicto con otros marcos Objective-C.
De todos modos, estoy comenzando esto y estoy decidiendo si publicarlo en SourceForge u otros sitios de alojamiento de código abierto.
Quiero saber si usted está interesado
Edición: He creado el proyecto, denominado BitArray, en SourceForge. La fuente está en el repositorio SF SVN y también he cargado un marco compilado. Este LINK tendrá su allí.
#define BITOP(a,b,op) \
((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))
no funcionará ...
Fix:
#define BITOP(a,b,op) \
((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))
¿Ha intentado buscar para ver si alguien ha escrito algo que se puede utilizar? La gente no solo va a escribir tu código por ti. –
En realidad, estaba tratando de compartir un código que había escrito haciendo una pregunta y respondiéndola, ¡pero este sitio es muy rápido! En los 10 minutos que tardé en preparar mi respuesta, ¡ya han aparecido dos respuestas! –
SO no está destinado a publicar preguntas que pueda contestar usted mismo. E incluso entonces, puede considerar buscar lo que existe sobre el tema en la web y comparar su enfoque con lo que encuentre, primero. –