ayuda. matriz binaria

Iniciado por xBurninGx, 14 Noviembre 2011, 03:19 AM

0 Miembros y 1 Visitante están viendo este tema.

xBurninGx

Hola,
    necesito crear una matriz eficiente que me marque según coordenadas X e Y si el valor almacenado es cierto o verdadero, y se me ha ocurrido hacer una matriz que en cada posición sólo contenga un bit, pero no se si eso se puede implementar, ya que sólo se me ocurre crear una matriz de char desperdiciando 7 bits por posición.

alguien me podría ayudar si ya se ha visto con el mismo problema?

muchas gracias de antemano.

Un saludo.

rir3760

Puedes utilizar un array de arrays de caracteres y utilizar cada uno de los bits del carácter para almacenar el estado (1/0 Verdadero/Falso). Así no habría desperdicio pero a cambio debes utilizar los operadores a nivel de bits para acceder y modificar el bit en cuestión.

¿Que lenguaje estas utilizando?

Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

BlackZeroX

#2
.
De manera MASIVA TODOS los elementos de tu matrix OCUPAN TODOS LOS BITS?... si solo ocupan algunos (Pero siempre dejan desocupados uno o mas bits pues usa esos bits como tu campo de flags, pero esto seria muy cochino)..

o puedes declarar una estructura de este tipo.



typedef struct StructData
{
    unsigned int uVal;
    char cChar;
} STRUCTDATA, *PSTRUCTDATA;



pero como te daras cuenta aun que si lo declaras una variable como char y suponiendo que unsigned int = 4 bytes y char = 1 byte es decir que la estructura pesara 5 bytes C dice que pesa 8 bytes (Se debe a la longitud de lectura de entero del procesador)...



printf("SizeOf(STRUCTDATA) = %d\n", sizeof(STRUCTDATA));



Asi que mejor declarar los flags como int en lugar de char...



typedef struct StructData
{
    unsigned int uVal;
    int iFlags;
} STRUCTDATA, *PSTRUCTDATA;



Dulces Lunas!¡.
The Dark Shadow is my passion.

xBurninGx

rir3760 es una opción pero algo tediosa de implementar no? tendría que crearme un traductor de direcciones ya que al método se le pasaría la coordenada X e Y y la tendría que ubicar en el bit de un char de una fila determinada.. aunque se podría hacer.. si no hay nada mejor, creo que es la solución que menos espacio me ocuparía..
Por cierto, el lenguaje en el que lo implementaría es en c++

BlackZeroX la cuestión es ahorrar espacio.. con tu implementación por lo que entiendo, cada dato supone 8 B, 64 bits, siendo necesario nada más que un bit.. me sale más rentable la matriz de char que por lo menos cada dato me supone 1B..

gracias a los dos.
un saludo.

do-while

#4
¡Buenas!

Siempre podras transformar la matriz en un vector:

Matriz m x n ->vector[m x n]
Matriz(i,j) ->vector[i * n + j] (0<= i < m, 0 <= j < n)

Ahora dada una matriz m x n, te hara falta almacenar m x n bits. Tomaremos como unidad del vector el byte (char). Asi, tendras que crear un vector de (m x n) / 8 + ((m x n) % 8 ? 1 : 0) bytes para poder almacenar todos los bits que te hagan falta.

Para acceder al elemento i , j:

- Tendras que saber el byte en el que se encuentra = numero de bits / 8 = (i * n + j) / 8
- Tendras que desplazarte dentro de ese byte (i * n + j) - ((i * n + j) / 8) * 8 bits a la izquierda (los bits totales de la posicion que buscas menos los la cantidad de bits de los bytes anteriores).

Por lo tanto el elemento i , j sera: vector[(i * n + j) / 8] >> (i * n + j) - ((i * n + j) / 8) * 8

¡Saludos!

PD: Si me he confundido con los calculos avisad, que lo he hecho un poco al vuelo.

¡Saludos de nuevo!

Advertencia - mientras estabas escribiendo, una nueva respuesta fue publicada. Probablemente desees revisar tu mensaje.


PD2: No me he dado cuenta de que lo he puesto mal.

Para saber el valor del bit tendras que hacer un and:
vector[(i * n + j) / 8] & (1 << 7 - ((i * n + j) - ((i * n + j) / 8) * 8))

para ponerlo a uno lo haces con un or:
vector[(i * n + j) / 8] | (1 << 7 - ((i * n + j) - ((i * n + j) / 8) * 8))

y para ponerlo a cero con xor (si no era cero, evidentemente, sino lo estarias poniendo a uno):
vector[(i * n + j) / 8] ^ (1 << 7 - ((i * n + j) - ((i * n + j) / 8) * 8))

Siempre podras ponerlo a cero de forma directa con la formula:
vector[(i * n + j) / 8] ^ (vector[(i * n + j) / 8] & (1 << 7 - ((i * n + j) - ((i * n + j) / 8) * 8)))

Ahora creo que esta bien.

La primera parte sirve solo para pensar un poco como hacerlo, pero esta mal. Lo dejo porque de los errores se aprende.

¡Saludos!
- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!

xBurninGx

sii.. gracias a la primera respuesta estaba pensando en algo así.. pero no me había parado a pensar en los cálculos todavia..
muchas gracias!! estudiaré bien sus fórmulas, que de primeras da un poco de miedo, jeje.

un saludo

BlackZeroX

Cita de: xBurninGx en 14 Noviembre 2011, 09:17 AM
BlackZeroX la cuestión es ahorrar espacio.. con tu implementación por lo que entiendo, cada dato supone 8 B, 64 bits, siendo necesario nada más que un bit.. me sale más rentable la matriz de char que por lo menos cada dato me supone 1B..

Cita de: BlackZeroX (Astaroth) en 14 Noviembre 2011, 07:50 AM.
De manera MASIVA TODOS los elementos de tu matrix OCUPAN TODOS LOS BITS?... si solo ocupan algunos (Pero siempre dejan desocupados uno o mas bits pues usa esos bits como tu campo de flags, pero esto seria muy cochino)..

Por ejemplo si cada elemento no se ocupa el bit 30 de manera general y nunca se llegara a ocupar... pues ocupa este bit para saber esto... el valor cambiara pero se arregla con una mascara de bits...

Dulces Lunas!¡.
The Dark Shadow is my passion.